Sorting jordan sequences in linear time using level-linked search trees

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

Research output: Contribution to journalArticlepeer-review

78 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)170-184
Number of pages15
JournalInformation and Control
Volume68
Issue number1-3
DOIs
StatePublished - 1986

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Sorting jordan sequences in linear time using level-linked search trees'. Together they form a unique fingerprint.

Cite this