Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees

For a Jordan curve C in the plane, let x sub 1, x sub 2,... , x sub 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 sub 1, x sub 2,..., x sub n a Jordan sequence. In this paper we describe an O(n)-time algorithm for recognizing and sorting Jordan sequences.