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:








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:




Note, Abstract, ©


(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},
ADDRESS = {San Francisco, USA},
ISBN = {0-89871-453-2},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ernst Althaus
Created
03/14/2000 11:26:57 AM
Revisions
9.
8.
7.
6.
5.
Editor(s)
Christine Kiesel
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Edit Dates
02.08.2005 16:16:40
05/02/2001 11:19:26 AM
21.03.2001 13:46:05
20.03.2001 17:21:25
14.03.2001 12:49:39
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section