Euclidean travelling salesman tour ($\mathrm{TS}(X)$)

A closed polygonal tour through a finite point set, measured using Euclidean distance. Write $\mathrm{TS}(X)$ for the minimum length over cyclic visiting orders. A two-point tour traverses its segment twice; a one-point tour has length zero. The triangle inequality allows repeated visits to be shortcut when estimating this minimum.

For every configuration $x$ in the unit square there are nonnegative weights $a_i(x)$ such that ${\sum }_i{a}_i(x{)}^2\le 16$ andUse the sums of the two incident edge lengths in a tour from the squared edge bound for tours in the unit square. Runs of missing vertices can be added by the cheaper of two out-and-back detours. This connects Euclidean travelling salesman tours to Talagrand's convex distance inequality.

Every finite point set in the unit square admits a cyclic visiting order with ${\sum }_i\Vert x_{i+1}-x_i{\Vert }^2\le 4$. Split the square into two right triangles, apply the quadratic path bound in a right triangle, and remove auxiliary corners using the law of cosines. The Cauchy-Schwarz inequality then gives $\mathrm{TS}(X)\le 2\sqrt{|X|}$. The tour minimizing ordinary length need not minimize the sum of squared lengths.

Given finitely many points in a right triangle with hypotenuse endpoints $a,b$, there is a path from $a$ to $b$ visiting them all with sum of squared edge lengths at most $\Vert a-b{\Vert }^2$. Repeated altitude subdivision reduces to cells containing one point. Joining the child paths preserves the squared-cost bound by the Pythagorean theorem; deleting an auxiliary right-angle vertex preserves it by the law of cosines.