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 - Saarländische Universitäts- und Landesbibliothek
AD - Postfach 151141, 66041 Saarbrücken
UR - http://scidok.sulb.uni-saarland.de/volltexte/2011/4212
ER -