Sorting Jordan sequences in linear time

Let C be a Jordan curve in the plane and let X J . X J , . . . be the abscissas of the intersection points of C with the x-axis, listed in the order the points occur on C. (See Figure 1). We call a sequence of real numbers x ) , x 2 > . . . , x n obtainable in this way a Jordan sequence. In this paper we consider the problem of recognizing and sorting Jordan sequences. The Jordan sequence sorting problem arises in at least two different contexts. Edelsbrunner [2] has posed the problem of computing the sorted list of intersections of a simple n-sides polygon with a line. This problem is linear-time equivalent to the problem of sorting a Jordan sequence, since we can represent the line parametrically and compute the list of intersections in the order they occur along the polygon in linear time by computing the intersection of the line with each side of the polygon. (We assume that the sides of the polygon are given in the order they occur along the polygon). Iri [6] has encountered the problem in the context of computational geography : for two Jordan curves A and B, we are given the list of their intersection points in the order they occur along A and asked to sort them in the order they occur along B, using as a unit-time primitive the operation of comparing two intersection points with respect to their order along B. Any comparison-based algorithm for the Jordan sequence sorting problem will solve Iri's problem as well. We call a Jordan sequence a Jordan Permutation if the sequence consists of the integers 1 through n in some order. Any Jordan permutation determines two nested sets of parentheses [9]. It follows that there are at most C n Jordan permutations of 1 through n, where c is a constant independent of n. This implies by a result of Fredman [3] that Jordan sequences can be sorted in 0(n) binary comparisons. Unfortunately the algorithm implied by Fredman's result has non-linear overhead. Our goal is to provide an algorithm that runs in linear time including overhead. Our approach to the Jordan sequence sorting problem is to convert it into a data manipulation problem that involves repeated splitting of lists. (The algorithm presented here was discovered by the first pair of authors and by the second pair of authors working independently. A sketch of the first pair's solution was presented in [4]).