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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ you should accept your answer $\endgroup$
    – miracle173
    Commented Jul 24, 2017 at 17:30

Your Answer

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

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