An instance of the curve reconstruction problem is a finite sample set V of
an unknown collection of curves. The task is to connect the points in V in
the order in which they lie on gamma. Giesen [ Proceedings of the 15th Ann
ual ACM Symposium on Computational Geometry (SCG '99), 1999, pp. 207-216] s
howed recently that the traveling salesman tour of V solves the reconstruct
ion problem for single closed curves under otherwise weak assumptions on ga
mma and V; gamma must be a single closed curve. We extend his result along
several directions:
we weaken the assumptions on the sample;
we show that traveling salesman-based reconstruction also works for single
open curves (with and without specified endpoints) and for collections of c
losed curves;
we give alternative proofs; and
we show that in the context of curve reconstruction, the traveling salesman
tour can be constructed in polynomial time.