Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26142
Titel: | Sorting Jordan sequences in linear time |
VerfasserIn: | Hoffmann, Kurt Mehlhorn, Kurt Rosenstiehl, Pierre Tarjan, Robert E. |
Sprache: | Englisch |
Erscheinungsjahr: | 1984 |
Quelle: | Saarbrücken, 1984 |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | For a Jordan curve C in the plane, let x_{1},x_{2},...,x_{n} be the abscissas of the intersection points of C with the x-axis, listed in the order the points occur on C. We call x_{1},x_{2},...,x_{n} a Jordan sequence. In this paper we describe an O(n)-time algorithm for recognizing and sorting Jordan sequences. The problem of sorting such sequences arises in computational geometry and computational geography. Our algorithm is based on a reduction of the recognition and sorting problem to a list-splitting problem. To solve the list-splitting problem we use level linked search trees. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-42129 hdl:20.500.11880/26198 http://dx.doi.org/10.22028/D291-26142 |
Schriftenreihe: | Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes |
Band: | 1984/09 |
Datum des Eintrags: | 7-Sep-2011 |
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 | |
---|---|---|---|---|
fb14_1984_09.pdf | 7,35 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.