Simplified linear-time Jordan sorting and polygon clipping

DOI10.1016/0020-0190(90)90111-AMaRDI QIDQ911762zbMATH OpenFDO

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)

zbMATH Keywords

analysis of algorithmscomputational geometrydata structures

Mathematics Subject Classification ID

Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Convex sets in (2) dimensions (including convex curves) (52A10)

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

Cites work

• A fast Las Vegas algorithm for triangulating a simple polygon
• Amortized Computational Complexity
• Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Finding Minimum-Cost Circulations by Successive Approximation
• On-line sorting of twisted sequences in linear time
• Reentrant polygon clipping
• Self-adjusting binary search trees
• Sorting jordan sequences in linear time using level-linked search trees

Cited in

(12)

• Sorting jordan sequences in linear time using level-linked search trees
• 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
• Computing optimal shortcuts for networks
• scientific article; zbMATH DE number 7561369 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 176247 (Why is no real title available?)
• Decision Trees for Geometric Models
• Three problems about simple polygons

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)