de.mpg.escidoc.pubman.appbase.FacesBean
English

Help Guide Privacy Policy Disclaimer Contact us

# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Traveling Salesman-Based Curve Reconstruction in Polynomial Time

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44003

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

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

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Althaus, E., & Mehlhorn, K. (2001). Traveling Salesman-Based Curve Reconstruction in Polynomial Time. SIAM Journal on Computing, 31, 27-66.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-313D-6
##### 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{Giesen:TSP} 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.