TY - JOUR
T1 - Sorting jordan sequences in linear time using level-linked search trees
AU - Hoffmann, Kurt
AU - Mehlhorn, Kurt
AU - Rosenstiehl, Pierre
AU - Tarjan, Robert E.
PY - 1986
Y1 - 1986
N2 - For a Jordan curve C in the plane nowhere tangent to the x axis, let x1, x2,..., xn be the abscissas of the intersection points of C with the x axis, listed in the order the points occur on C. We call x1, x2,..., xn 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.
AB - For a Jordan curve C in the plane nowhere tangent to the x axis, let x1, x2,..., xn be the abscissas of the intersection points of C with the x axis, listed in the order the points occur on C. We call x1, x2,..., xn 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.
UR - http://www.scopus.com/inward/record.url?scp=0022436559&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022436559&partnerID=8YFLogxK
U2 - 10.1016/S0019-9958(86)80033-X
DO - 10.1016/S0019-9958(86)80033-X
M3 - Article
AN - SCOPUS:0022436559
SN - 0019-9958
VL - 68
SP - 170
EP - 184
JO - Information and Control
JF - Information and Control
IS - 1-3
ER -