Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a polynomial time algorithm that finds this?

Just interested.

Thanks in advance

edit: In this case you are given a set of cartesian co-ordinates that represents their physical distance from one another.

share|cite|improve this question
What you are describing is the Traveling Salesman Problem, which is thought to have no polynomial time solution. – A.E Jun 29 '13 at 4:35
Actually I thought it was kind of different, the TSP involves weighted graph, I'm talking about a set of co-ordinates on some two dimensional plane, or at least that's what I thought "points" would convey. – user84348 Jun 29 '13 at 5:20
I'm not convinced the weighted graph can always be converted to a cartesian co-ordinate system. – user84348 Jun 29 '13 at 5:54
If you are given a set of points in the Cartesian plane, you can construct a corresponding weighted graph for the TSP by weighting each edge between any two points according to the distance between them, using the formula: $$ \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} $$ – Adriano Jun 29 '13 at 6:29
Sorry, Adriano I'm not asking to convert it that way round. Obviously you could solve my problem using TSP solutions, but I'm trying to ascertain whether this version of the problem (cartesian points) is simplified because I have cartesian values, and thus may not require exponential time solutions. – user84348 Jun 29 '13 at 6:44
up vote 4 down vote accepted

According to Wikipedia, the Euclidean traveling salesman problem is NP-complete, which implies that there is no known polynomial algorithm for finding the optimal solution. The Euclidean metric does simplify things, however, making it easier to find good approximative solutions, as described in the Wikipedia article on TSP.

share|cite|improve this answer
Thanks. Next time I'll be sure to phrase my question better, don't like them down votes. – user84348 Jun 29 '13 at 11:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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