Simplified linear-time Jordan sorting and polygon clipping
From MaRDI portal
Publication:911762
DOI10.1016/0020-0190(90)90111-AzbMath0697.68036MaRDI QIDQ911762
Robert Endre Tarjan, Khun Yee Fung, Tina M. Nicholl, Christopher J. Van Wyk
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10) Data structures (68P05)
Related Items (10)
OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ Three problems about simple polygons ⋮ Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures ⋮ Computing optimal shortcuts for networks ⋮ Unnamed Item ⋮ A fast Las Vegas algorithm for triangulating a simple polygon ⋮ A new algorithm for Jordan sorting: Its average-case analysis ⋮ Quadtree, ray shooting and approximate minimum weight Steiner triangulation ⋮ Translating a convex polyhedron over monotone polyhedra ⋮ Decision Trees for Geometric Models
Cites Work
- On-line sorting of twisted sequences in linear time
- A fast Las Vegas algorithm for triangulating a simple polygon
- Reentrant polygon clipping
- Finding Minimum-Cost Circulations by Successive Approximation
- Amortized Computational Complexity
- Self-adjusting binary search trees
- Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Sorting jordan sequences in linear time using level-linked search trees
This page was built for publication: Simplified linear-time Jordan sorting and polygon clipping
