Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-25679
Titel: | Curve reconstruction and the traveling salesman problem |
VerfasserIn: | Althaus, Ernst |
Sprache: | Englisch |
Erscheinungsjahr: | 2001 |
Kontrollierte Schlagwörter: | Punktmenge ; Kurve ; Rekonstruktion ; Algorithmus ; Travelling-salesman-Problem |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Dissertation |
Abstract: | An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves gamma. The task is to connect the points in V in the order in which they lie on gamma. Giesen [Proceedings of the 15th Annual ACM Symposium on Computational Geometry (SCG '99), 1999, pp. 207--216] showed recently that the traveling salesman tour of V solves the reconstruction problem for single closed curves under otherwise weak assumptions on gamma and V; gamma must be a single closed curve. We extend his result along several directions: * we weaken the assumptions on the sample; * we show that traveling salesman-based reconstruction also works for single open curves (with and without specified endpoints) and for collections of closed curves; * we give alternative proofs; and * we show that in the context of curve reconstruction, the traveling salesman tour can be constructed in polynomial time. Furthermore we report on experiments with a number of recent curve reconstruction algorithms. Die Eingabe eines Kurvenkonstruktionsproblems ist eine endliche Menge V von Sammelpunkten auf einer unbekannten Kurve Gamma. Die Aufgabe besteht darin einen Graphen G=(V,E) zu konstruieren, in dem zwei Punkte genau dann durch eine Kante verbunden sind, wenn die Punkte in Gamma benachbart sind. Giesen hat kuerzlich gezeigt, dass die Traveling Salesman Tour durch die Punkte V das Kurvenkonstruktionsproblem fuer einzelne geschlossene Kurven unter ansonsten schwachen Bedingungen loest; Gamma muss allerdings eine einzelne geschlossene Kurve sein. Wir erweitern dieses Ergebnis in mehrere Richtungen. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-1438 hdl:20.500.11880/25735 http://dx.doi.org/10.22028/D291-25679 |
Erstgutachter: | Kurt Mehlhorn |
Tag der mündlichen Prüfung: | 27-Apr-2001 |
Datum des Eintrags: | 12-Feb-2004 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
ErnstAlthaus_ProfDrKurtMehlhorn.pdf | 1,77 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.