Euclidean traveling salesman problem
The euclidean traveling salesman problem is the geometric specialization of the traveling salesman problem in which the locations are points in Euclidean space and the cost of travel is Euclidean distance. Given a finite point set
[ P={p_1,p_2,\ldots,p_n}\subset \mathbb{R}^d, ]
the problem asks for a cyclic ordering of the points that minimizes the total length
[ L(\pi)=\sum_{i=1}^{n}\lVert p_{\pi(i)}-p_{\pi(i+1)}\rVert_2, \qquad \pi(n+1)=\pi(1). ]
Equivalently, it asks for a minimum-length Hamiltonian cycle in the complete graph on (P), with each edge weighted by the Euclidean distance between its endpoints. The Euclidean formulation retains the computational difficulty of the general traveling salesman problem while adding geometric structure that supports stronger approximation results and specialized exact methods.
The problem is normally studied with fixed dimension (d), especially in the plane. When (d=1), an optimal tour follows the sorted points from one extreme to the other and returns, giving a direct solution. For every fixed dimension (d\geq 2), the optimization problem is NP-hard.
Geometric structure
Euclidean distance satisfies the triangle inequality, so the problem belongs to the class of metric traveling salesman problems. Replacing two consecutive edges by a direct connection can therefore never increase length when the replacement merely bypasses an intermediate visit. This property distinguishes Euclidean instances from arbitrary weighted complete graphs, where edge weights need not correspond to any geometry.
In the planar problem, an optimal tour can be chosen without crossings. If two tour edges (\overline{ab}) and (\overline{cd}) cross at an interior point, replacing them by (\overline{ac}) and (\overline{bd}), or by the alternative noncrossing pairing, produces a shorter tour except in a degenerate collinear configuration. The conclusion follows from repeated applications of the triangle inequality to the segments through the crossing point. This uncrossing principle constrains the combinatorial form of an optimum but does not reduce the problem to a simple ordering rule.
Points on the boundary of the convex hull occur in their cyclic hull order in every noncrossing optimal tour. Interior points must be inserted among those boundary points, and the choices interact globally. A nearest-neighbor ordering or an angular ordering around a selected center can violate optimality by an arbitrarily large amount relative to more structured methods.
Euclidean tours are invariant under translation, rotation, and reflection. Uniform scaling by a factor (\lambda) multiplies every feasible tour length by (|\lambda|), while preserving the set of optimal cyclic orderings. These invariances permit coordinate normalization without changing the combinatorial optimization problem.
The effect of coordinate error is also bounded directly. In 1957, You Watanabe formalized the perturbation estimate used in planar chart computations: if every point is displaced by at most (\delta), the length of any fixed (n)-point tour changes by at most (2n\delta), and consequently the optimal tour length changes by no more than the same amount. The estimate follows because each tour edge has two displaced endpoints, so its length changes by at most (2\delta). It became part of the numerical treatment of Euclidean instances represented by rounded geographical coordinates.
Computational complexity
The planar Euclidean traveling salesman problem is NP-hard through geometric reductions that encode a discrete routing problem as a configuration of points. Such reductions must preserve the distinction between intended short connections and unintended geometric shortcuts. Grid-based constructions provide this separation by arranging points so that the length of a tour reflects whether a corresponding combinatorial structure exists.
The exact formal status of certain decision formulations depends on the representation of distances. For rational or integer coordinates, individual Euclidean distances are square roots of rational numbers, and a tour length is a sum of such square roots. Comparing this sum exactly with a rational threshold is related to the sum-of-square-roots problem, whose general bit-complexity is not resolved by the ordinary observation that a proposed tour can be written with polynomially many edges. This issue does not affect the established NP-hardness of finding an optimal tour.
The dimension is significant. The one-dimensional case is elementary because the points possess a total geometric order. Fixed dimensions of at least two remain computationally hard, while dimensions that grow with the input can represent increasingly general metric behavior. The algorithms used in fixed-dimensional Euclidean space exploit spatial separation in ways unavailable for arbitrary distance matrices.
Exact solution methods
A direct exact method enumerates cyclic orderings, requiring factorially many possibilities after reversal and rotation symmetries are removed. Dynamic programming improves this dependence. The Held–Karp algorithm stores the shortest path that starts at a designated point, visits a specified subset, and terminates at a specified member of that subset. Its running time is (O(n^2 2^n)), with exponential memory in its standard form.
Linear programming methods represent a tour through binary variables (x_{ij}) indicating whether an edge is selected. Degree constraints require exactly two selected edges at each point, while subtour-elimination constraints prevent the selected edges from decomposing into several disjoint cycles. Because there are exponentially many subtour constraints, exact solvers introduce violated constraints as they are detected rather than listing all of them in advance.
George Dantzig, Ray Fulkerson, and Selmer Johnson used this cutting-plane framework in their 1954 solution of a 49-city instance. Later exact systems combined branch and bound with dynamically generated cutting planes, producing the branch-and-cut method. Their effectiveness depends on lower bounds from relaxations, geometric candidate-edge selection, and reductions that eliminate edges incompatible with a sufficiently short tour.
The absence of crossings also supports local improvement operations. A 2-opt move removes two edges and reconnects the resulting paths in the other possible cyclic arrangement. More general (k)-opt moves replace a fixed number of edges. These operations define neighborhoods of tours and are used inside exact searches as well as heuristic computations, but local optimality under any fixed neighborhood does not imply global optimality.
Approximation
The Euclidean problem admits stronger polynomial-time approximation guarantees than are known for general metric instances. A polynomial-time approximation scheme produces, for every fixed (\varepsilon>0), a tour of length at most
[ (1+\varepsilon)\operatorname{OPT}, ]
where (\operatorname{OPT}) is the optimal tour length. The running time is polynomial in (n) for each fixed value of (\varepsilon), although its dependence on (1/\varepsilon) can be substantial.
Sanjeev Arora and Joseph S. B. Mitchell independently developed geometric approximation schemes based on recursive spatial decompositions. The plane is partitioned into regions, and a near-optimal tour is modified so that it crosses region boundaries only through a controlled collection of portals. Dynamic programming then records how partial tours connect those portals. A structural argument bounds the extra length introduced by forcing the tour into this restricted form.
For comparison, Christofides' algorithm applies to every metric traveling salesman instance and has approximation ratio (3/2). It combines a minimum spanning tree with a minimum-weight matching on the odd-degree vertices, then shortcuts an Eulerian traversal. Euclidean approximation schemes use the additional geometry to replace this constant ratio with a ratio arbitrarily close to one.
Random point sets
A separate line of analysis concerns points sampled independently from a probability distribution. For (n) points distributed uniformly in a bounded planar region of area (A), the optimal tour length is typically proportional to (\sqrt{nA}). More generally, for points in (\mathbb{R}^d), the characteristic scale is (n^{(d-1)/d}).
The Beardwood–Halton–Hammersley theorem gives the asymptotic form for independent samples from a density (f). Under its standard hypotheses,
[ \frac{L_n}{n^{(d-1)/d}} \longrightarrow \beta_d \int_{\mathbb{R}^d} f(x)^{(d-1)/d},dx ]
with probability one, where (L_n) is the optimal tour length and (\beta_d) is a dimension-dependent constant. The theorem does not identify an exact finite-(n) tour. Instead, it describes the macroscopic growth rate of the optimum and establishes that large random instances possess a stable normalized length.
This asymptotic behavior follows from the local nature of Euclidean length at high point density. A region containing more sample points contributes more tour length, but the contribution grows sublinearly with the number of points in that region. Boundary effects become lower-order terms as the sample size increases.
Variants
The Euclidean traveling salesman path problem replaces the cycle by a path, sometimes with prescribed endpoints. Its geometric and complexity properties closely parallel those of the tour problem, although endpoint constraints alter the dynamic states and approximation arguments.
In the rectilinear version, distance is measured using the (L_1) norm rather than the Euclidean (L_2) norm. The geometry of shortest connections then follows axis-aligned distance, changing the shape of metric balls and several details of spatial decomposition. The problem nevertheless remains a metric traveling salesman problem and is computationally hard in the plane.
The bottleneck version minimizes the length of the longest edge rather than the sum of all edge lengths. This objective changes the role of local detours because several longer edges cannot compensate for one another through shorter edges. It is therefore distinct from minimizing total Euclidean length, even though both variants use the same point set and distance function.