Planar lower envelope of monotone polygonal chains

DOI10.1016/j.ipl.2015.07.004zbMath1338.68266arXiv1412.6619OpenAlexW1482125056MaRDI QIDQ495682

Daniel L. Lu

Publication date: 15 September 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.6619

zbMATH Keywords

computational geometryoutput-sensitive algorithmslower envelopeupper envelope

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Uses Software

• CGAL

Cites Work

• Finding the upper envelope of n line segments in O(n log n) time
• Corrections to Lee's visibility polygon algorithm
• Visibility queries and maintenance in simple polygons
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Efficient visibility queries in simple polygons
• Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel
• Query point visibility computation in polygons with holes
• A linear algorithm for computing the visibility polygon from a point
• An Optimal Algorithm for Computing Visibility in the Plane
• An Output-Sensitive Convex Hull Algorithm for Planar Objects

This page was built for publication: Planar lower envelope of monotone polygonal chains