Simplified linear-time Jordan sorting and polygon clipping
From MaRDI portal
Publication:911762
DOI10.1016/0020-0190(90)90111-AzbMATH Open0697.68036MaRDI QIDQ911762FDOQ911762
Authors: Khun Yee Fung, Tina M. Nicholl, Robert E. Tarjan, Christopher J. Van Wyk
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 1919433
- Near optimal line segment queries in simple polygons
- Linear-time algorithms for weakly-monotone polygons
- A randomized algorithm for triangulating a simple polygon in linear time
- A linear time algorithm for computing the convex hull of an ordered crossing polygon
- Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
- LATIN 2004: Theoretical Informatics
- A LINEAR-TIME RANDOMIZED ALGORITHM FOR THE BOUNDED VORONOI DIAGRAM OF A SIMPLE POLYGON
- Memory-constrained algorithms for simple polygons
- scientific article; zbMATH DE number 4045150
Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Convex sets in (2) dimensions (including convex curves) (52A10)
Cites Work
- Finding Minimum-Cost Circulations by Successive Approximation
- Self-adjusting binary search trees
- Reentrant polygon clipping
- Amortized Computational Complexity
- 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
- A fast Las Vegas algorithm for triangulating a simple polygon
- On-line sorting of twisted sequences in linear time
Cited In (12)
- Quadtree, ray shooting and approximate minimum weight Steiner triangulation
- Translating a convex polyhedron over monotone polyhedra
- A fast Las Vegas algorithm for triangulating a simple polygon
- Title not available (Why is that?)
- Computing optimal shortcuts for networks
- Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
- OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
- A new algorithm for Jordan sorting: Its average-case analysis
- Title not available (Why is that?)
- Decision Trees for Geometric Models
- Three problems about simple polygons
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911762)