Editing Travelling salesman problem (section)

===Euclidean===
<!-- linked from redirect [[Euclidean TSP]] -->
For points in the [[Euclidean plane]], the optimal solution to the travelling salesman problem forms a [[simple polygon]] through all of the points, a [[polygonalization]] of the points.<ref>{{cite journal
 | last1 = Quintas | first1 = L. V.
 | last2 = Supnick | first2 = Fred
 | doi = 10.2307/2313333
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2313333
 | mr = 188872
 | pages = 977–980
 | title = On some properties of shortest Hamiltonian circuits
 | volume = 72
 | year = 1965| issue = 9
 }}</ref> Any non-optimal solution with crossings can be made into a shorter solution without crossings by local optimizations. The [[Euclidean distance]] obeys the triangle inequality, so the Euclidean TSP forms a special case of metric TSP. However, even when the input points have integer coordinates, their distances generally take the form of [[square root]]s, and the length of a tour is a [[sum of radicals]], making it difficult to perform the [[symbolic computation]] needed to perform exact comparisons of the lengths of different tours.

Like the general TSP, the exact Euclidean TSP is NP-hard, but the issue with sums of radicals is an obstacle to proving that its decision version is in NP, and therefore NP-complete. A discretized version of the problem with distances rounded to integers is NP-complete.{{sfnp|Papadimitriou|1977}} With rational coordinates and the actual Euclidean metric, Euclidean TSP is known to be in the Counting Hierarchy,{{sfnp|Allender|Bürgisser|Kjeldgaard-Pedersen|Mitersen|2007}} a subclass of PSPACE. With arbitrary real coordinates, Euclidean TSP cannot be in such classes, since there are uncountably many possible inputs. Despite these complications, Euclidean TSP is much easier than the general metric case for approximation.{{sfnp|Larson|Odoni|1981}} For example, the minimum spanning tree of the graph associated with an instance of the Euclidean TSP is a [[Euclidean minimum spanning tree]], and so can be computed in expected ''O''(''n'' log ''n'') time for ''n'' points (considerably less than the number of edges). This enables the simple 2-approximation algorithm for TSP with triangle inequality above to operate more quickly.

In general, for any ''c'' > 0, where ''d'' is the number of dimensions in the Euclidean space, there is a polynomial-time algorithm that finds a tour of length at most (1 + 1/''c'') times the optimal for geometric instances of TSP in

:<math>O{\left(n (\log n)^{O(c \sqrt{d})^{d-1}}\right)}</math>

time; this is called a [[polynomial-time approximation scheme]] (PTAS).{{sfnp|Arora|1998}} [[Sanjeev Arora]] and [[Joseph S. B. Mitchell]] were awarded the [[Gödel Prize]] in 2010 for their concurrent discovery of a PTAS for the Euclidean TSP.

In practice, simpler heuristics with weaker guarantees continue to be used.