TSP-Based Curve Reconstruction in Polynomial Time

Althaus, Ernst; Mehlhorn, Kurt

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

TSP-Based Curve Reconstruction in Polynomial Time

MPS-Authors

/persons/resource/persons44003

Althaus, Ernst
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Althaus, E., & Mehlhorn, K. (2000). TSP-Based Curve Reconstruction in Polynomial Time. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00) (pp. 686-695). New York, USA: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3336-4

Abstract

An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$. Giesen~\cite{SCG99*207} showed recently that the Traveling Salesman tour 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, give an alternate proof, and show that in the context of curve reconstruction, the Traveling Salesman tour can be constructed in polynomial time.