# Sorting Jordan sequences in linear time

Kurt Hoffmann, Kurt Hehlhoph, Pierre Rosenstiehl, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

## Abstract

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  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  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 . 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  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 ).

Original language English (US) Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 Association for Computing Machinery, Inc 196-203 8 0897911636, 9780897911634 https://doi.org/10.1145/323233.323259 Published - Jun 1 1985 Yes 1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United StatesDuration: Jun 5 1985 → Jun 7 1985

### Publication series

Name Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985

### Other

Other 1st Annual Symposium on Computational Geometry, SCG 1985 United States Baltimore 6/5/85 → 6/7/85

## All Science Journal Classification (ASJC) codes

• Computational Mathematics
• Geometry and Topology

## Fingerprint

Dive into the research topics of 'Sorting Jordan sequences in linear time'. Together they form a unique fingerprint.