Published in Discrete & Computational Geometry in 2000, this research explores the profound mathematical link between the Traveling Salesman Problem (TSP) and the geometry of continuous curves. It establishes the specific conditions under which solving a TSP on a set of points sampled from a curve will perfectly reconstruct that curve, formalizing a 70-year-old intuition by Karl Menger.
The Problem of Curve Reconstruction
Curve reconstruction is a core challenge in computer vision and computational geometry: given a "point cloud" sampled from an unknown curve, how can we connect them to recover the original shape? While specialized algorithms like the "Crust" exist, a natural approach is the Traveling Salesman Problem—finding the shortest path that visits every point.
Intuitively, if points are sufficiently dense, the shortest path should follow the curve. However, this paper demonstrates that smoothness alone is insufficient. The author seeks to define the exact "regularity" conditions that make the TSP a reliable tool for reconstruction.
Methods: From Local Projections to Global Paths
The author employs a "local-to-global" proof strategy involving several key mathematical frameworks:
- Local Analysis via Projections: Using Reshetnyak’s Theorem from integral geometry, the paper relates the length of a curve to the average length of its orthogonal projections. By proving the correct reconstruction is the shortest "on average" across projections in a small neighborhood, the author establishes the local case.
- Generalizing Menger’s Theorem: In 1930, Karl Menger proposed that curve length is the supremum of the lengths of the shortest paths through its finite subsets. The author generalizes this to simple closed curves in Euclidean space.
- Global Transition: Using the generalized Menger's theorem and Hausdorff measures, the paper proves that if local conditions are met everywhere, the global TSP solution must coincide with the curve's natural order.
Key Insights: Why Smoothness Fails
The paper identifies s-regularity as the crucial requirement. A curve is s-regular if it has non-zero left and right tangents at every point, and the angle between these tangents is less than $\pi$ (no "infinitely sharp" cusps).
As shown in the figure above, even if a curve has finite total absolute curvature, it can "trick" the TSP. In this example (a unit interval on the x-axis joined with $y=x^2$), the TSP might choose a shortcut between the two branches rather than following the path through the origin. This reinforces the idea that the TSP is fundamentally baked into the definition of "length" for continuous objects.
Key Results
- The Main Theorem: For a simple curve $\gamma$ satisfying regularity conditions (tangents exist and angle $< \pi$), there exists a sampling density such that the TSP path (for open curves) or tour (for closed curves) is the unique, correct reconstruction.
- Menger Equivalence: The paper successfully proves the equivalence between the standard definition of arc length and Menger’s "messenger problem" definition for a wider class of curves than previously established.
Limitations and Future Work
While the theorem guarantees success for "sufficiently dense" samples, it requires a global bound. In practice, different parts of a curve might need varying sampling densities (e.g., more points near sharp turns). Later work has addressed this using "local feature size," though often assuming more smoothness than required here. Additionally, while the TSP is generally NP-hard, the author notes that for these specific dense samples from plane curves, the problem can actually be solved in polynomial time.
Summary updated