4
$\begingroup$

I have a set of points in a 2D plane. I'm searching for an algorithm that:

  • Draws a continuous line passing through all the points starting from a random point.
  • Optimizes for the minimum total line length in Euclidean distance.
  • The line should end at the point it started but not cross any other point more than once.

In plain terms, suppose we had a paper with N dots on it. We'd take a pencil starting from a random point and try to go through all the points without lifting the pencil and conclude by reaching the point we started at.

I looked into Euclidian minimum spanning tree, but what I'm looking for is a closed loop and not a graph-tree like line. What I'd like in approximation is a Convex Hull that would go through all the points and not just form the perimeter.

Can someone direct me to the right family of algorithms?

David Richerby
82.5k26 gold badges146 silver badges239 bronze badges
asked Jun 24, 2017 at 12:03
$\endgroup$

1 Answer 1

1
$\begingroup$

Turns out what I'm looking for is the Travelling salesman problem.

answered Jun 24, 2017 at 12:27
$\endgroup$
1
  • 1
    $\begingroup$ you should accept your answer $\endgroup$ Commented Jul 24, 2017 at 17:30

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.