TSP-based curve reconstruction in polynomial time. (English) Zbl 0954.65011

Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms. San Francisco, CA, USA, January 9-11, 2000. Philadelphia, PA: SIAM. 686-695 (2000).
Summary: An instance of the curve reconstruction problem is a finite sample set \(V\) of an unknown curve \(\gamma\) and the task is to connect the points in \(V\) in the order in which they lie on \(\gamma\). J. Giesen [Curve reconstruction the TSP, and Menger’s theorem on length. In Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG’99), 207-216 (1999)] showed recently that the traveling salesman path (TSP) of \(V\) solves the reconstruction problem under fairly week assumptions on \(\gamma\) and \(V\). We extend his result along three dimensions. We weaken the assumptions, we give an alternate proof, and we show that in the context of curve reconstruction the traveling salesman tour can be constructed in polynomial time.
For the entire collection see [Zbl 0933.00039].


65D17 Computer-aided design (modeling of curves and surfaces)
65K05 Numerical mathematical programming methods
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization