TY  - RPRT
T1  - Sorting Jordan sequences in linear time
T3  - Saarbrücken, 1984
A1  - Hoffmann,Kurt
A1  - Mehlhorn,Kurt
A1  - Rosenstiehl,Pierre
A1  - Tarjan,Robert E.
Y1  - 2011/09/07
N2  - 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.
CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/4212
ER  -