3
$\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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ you should accept your answer $\endgroup$ – miracle173 Jul 24 '17 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.