MPI-INF D1 Publications: Journal Article: Traveling Salesman-Based Curve Reconstruction in Polynomial Time

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

Althaus, Ernst
Mehlhorn, Kurt

dblp
dblp

BibTeX cite key*:

AltMeh2001j

Title

Title*:	Traveling Salesman-Based Curve Reconstruction in Polynomial Time
Attachment(s):	Mehlhorn_a_2001_j.pdf (622.3 KB); 143.pdf (576.35 KB)

Journal

Journal Title*:	SIAM Journal on Computing	Journal's URL:	http://www.siam.org/journals/sicomp/sicomp.htm
Download URL for the article:	http://siamdl.aip.org/getpdf/servlet/GetPDFServlet?filetype=pdf&id=SMJCAT000031000001000027000001&idtype=cvips http://epubs.siam.org/sam-bin/dbq/article/36611	Language:	English

Publisher

Publisher's Name:	SIAM	Publisher's URL:	http://www.siam.org
Publisher's Address:	Philadelphia, USA	ISSN:	0097-5397

Vol, No, pp, Date

Volume*:	31	Number:	1
Publishing Date:	2001
Pages*:	27-66	Number of VG Pages:
Page Start:		Page End:
Sequence Number:		DOI:

Note, Abstract, ©

Note:
(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{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.
URL for the Abstract:
Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
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, VG Wort

BibTeX Entry:

@ARTICLE{AltMeh2001j,
AUTHOR = {Althaus, Ernst and Mehlhorn, Kurt},
TITLE = {Traveling Salesman-Based Curve Reconstruction in Polynomial Time},
JOURNAL = {SIAM Journal on Computing},
PUBLISHER = {SIAM},
YEAR = {2001},
NUMBER = {1},
VOLUME = {31},
PAGES = {27--66},
ADDRESS = {Philadelphia, USA},
ISBN = {0097-5397},
}

Entry last modified by Tamara Hausmann, 03/02/2010

Edit History (please click the blue arrow to see the details)

	Editor(s) Ernst Althaus	Created 07/19/2001 08:14:19 PM
Revisions 6. 5. 4. 3. 2.	Editor(s) Tamara Hausmann Christine Kiesel Christine Kiesel Tamara Hausmann Tamara Hausmann	Edit Dates 09.11.2006 14:34:35 04.10.2006 10:13:40 29.09.2006 14:36:32 20.06.2006 12:15:03 22.03.2002 13:33:09

Attachment Section

View attachments here:

Mehlhorn_a_2001_j.pdf

143.pdf