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

DOI10.1016/S0019-9958(86)80033-XzbMath0614.68051OpenAlexW2085041675MaRDI QIDQ4721658

Pierre Rosenstiehl, Kurt Mehlhorn, Kurt Hoffmann, Robert Endre Tarjan

Publication date: 1986

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80033-x

zbMATH Keywords

sortingcomputational geometrylinear timeJordan curvecomputational geographyJordan sequencelevel-linked search treeslist-splitting problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies and applications (68U99)

Related Items (44)

On-line sorting of twisted sequences in linear time ⋮ Decomposition and intersection of simple splinegons ⋮ Meanders and the Temperley-Lieb algebra ⋮ TOPOLOGICAL PEELING AND APPLICATIONS ⋮ GOOD NEWS: PARTITIONING A SIMPLE POLYGON BY COMPASS DIRECTIONS ⋮ Scaffold permutations ⋮ Randomized search trees ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ Cartographic line simplication and polygon CSG formulae in O(n log* n) time ⋮ Generating cyclic rotation Gray codes for stamp foldings and semi-meanders ⋮ Three problems about simple polygons ⋮ Improved bounds for finger search on a RAM ⋮ Computational geometry in a curved world ⋮ Simplified linear-time Jordan sorting and polygon clipping ⋮ Triangulating a simple polygon in linear time ⋮ Arrangements of curves in the plane --- topology, combinatorics, and algorithms ⋮ Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures ⋮ SU(N) meander determinants ⋮ Interval-based temporal functional dependencies: specification and verification ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ Meander, folding, and arch statistics ⋮ Exact meander asymptotics: a numerical check ⋮ A linear time algorithm to remove winding of a simple polygon ⋮ Efficient on-line algorithms for Euler diagram region computation ⋮ Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons ⋮ Computing the \(k\)-visibility region of a point in a polygon ⋮ Placing Text Boxes on Graphs ⋮ Optimal finger search trees in the pointer machine ⋮ Finding and counting permutations via CSPs ⋮ Partitioning the meandering curves ⋮ Topologically sweeping visibility complexes via pseudotriangulations ⋮ Meanders: A direct enumeration approach ⋮ Nested Sets of Pairs ⋮ A partial order for the set of meanders ⋮ Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time ⋮ A fast Las Vegas algorithm for triangulating a simple polygon ⋮ Clamshell casting ⋮ Meanders: Exact asymptotics ⋮ A new algorithm for Jordan sorting: Its average-case analysis ⋮ Translating a convex polyhedron over monotone polyhedra ⋮ A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons ⋮ Decision Trees for Geometric Models ⋮ Linear-Time Algorithm for Long LCF with k Mismatches ⋮ A workbench for computational geometry

This page was built for publication: Sorting jordan sequences in linear time using level-linked search trees