Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Althaus, Ernst Mehlhorn, Kurt dblp dblp
 Editor(s):
 BibTeX cite key*: AlthausMehlhorn1999

 Title, Booktitle
 Title*: TSP-Based Curve Reconstruction in Polynomial Time Booktitle*: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00)

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da00/ URL for downloading the paper: Event Address*: San Francisco, USA Language: English Event Date* (no longer used): January, 9-11 Organization: ACM Special Interest Group on Algorithms and Computation Theory and SIAM Activity Group on Discrete Mathematics Event Start Date: 9 January 2000 Event End Date: 11 January 2000

 Publisher
 Name*: ACM URL: http://www.acm.org/ Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: Pages: 686-695 Year*: 2000 VG Wort Pages: ISBN/ISSN: 0-89871-453-2 Sequence Number: DOI:

 (LaTeX) 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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:

@INPROCEEDINGS{AlthausMehlhorn1999,
AUTHOR = {Althaus, Ernst and Mehlhorn, Kurt},
TITLE = {TSP-Based Curve Reconstruction in Polynomial Time},
BOOKTITLE = {Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-00)},
PUBLISHER = {ACM},
YEAR = {2000},
ORGANIZATION = {ACM Special Interest Group on Algorithms and Computation Theory and SIAM Activity Group on Discrete Mathematics},
PAGES = {686--695},