Eingang zum Volltext in SciDok
Lizenz
Report (Bericht) zugänglich unter
Sorting Jordan sequences in linear time
URN: urn:nbn:de:bsz:291-scidok-42129
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4212/
Quelle:
(1984) Saarbrücken, 1984
pdf-Format:
Dokument 1.pdf (7.352 KB)
Institut:
Fachrichtung 6.2 - Informatik
DDC-Sachgruppe:
Informatik
Dokumentart:
Report (Bericht)
Schriftenreihe:
Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Bandnummer:
1984/09
Sprache:
Englisch
Erstellungsjahr:
1984
Publikationsdatum:
07.09.2011
Kurzfassung auf Englisch:
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.
Lizenz:
Standard-Veröffentlichungsvertrag