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

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985
PublisherAssociation for Computing Machinery, Inc
Pages196-203
Number of pages8
ISBN (Electronic)0897911636, 9780897911634
DOIs
StatePublished - Jun 1 1985
Externally publishedYes
Event1st Annual Symposium on Computational Geometry, SCG 1985 - Baltimore, United States
Duration: Jun 5 1985Jun 7 1985

Publication series

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

Other

Other1st Annual Symposium on Computational Geometry, SCG 1985
CountryUnited States
CityBaltimore
Period6/5/856/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.

  • Cite this

    Hoffmann, K., Hehlhoph, K., Rosenstiehl, P., & Tarjan, R. E. (1985). Sorting Jordan sequences in linear time. In Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985 (pp. 196-203). (Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985). Association for Computing Machinery, Inc. https://doi.org/10.1145/323233.323259