Planar lower envelope of monotone polygonal chains

DOI10.1016/J.IPL.2015.07.004MaRDI QIDQ495682zbMATH OpenOpenAlexFDO

Authors 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 geometrylower envelopeoutput-sensitive algorithmsupper envelope

Mathematics Subject Classification ID

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

Abstract: A simple linear search algorithm running in $O(n+mk)$ time is proposed for constructing the lower envelope of $k$ vertices from $m$ monotone polygonal chains in 2D with $n$ vertices in total. This can be applied to output-sensitive construction of lower envelopes for arbitrary line segments in optimal $O(nlogk)$ time, where $k$ is the output size. Compared to existing output-sensitive algorithms for lower envelopes, this is simpler to implement, does not require complex data structures, and is a constant factor faster.

Recommendations

• A simple algorithm for determining the envelope of a set of lines
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• Finding the upper envelope of n line segments in O(n log n) time
• The upper envelope of piecewise linear functions: Algorithms and applications
• Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel

Cites work

• 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
• Corrections to Lee's visibility polygon algorithm
• Efficient visibility queries in simple polygons
• Finding the upper envelope of n line segments in O(n log n) time
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel
• Query point visibility computation in polygons with holes
• Visibility queries and maintenance in simple polygons

Describes a project that uses

Uses Software

• CGAL

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q495682)