Traveling salesman-based curve reconstruction in polynomial time

Citation
E. Althaus et K. Mehlhorn, Traveling salesman-based curve reconstruction in polynomial time, SIAM J COMP, 31(1), 2001, pp. 27-66
Citations number
18
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
27 - 66
Database
ISI
SICI code
0097-5397(20010729)31:1<27:TSCRIP>2.0.ZU;2-5
Abstract
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.