Planar lower envelope of monotone polygonal chains

2014/12/20 by Daniel Lu, Daniel L. Lu, Lu, Daniel
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.1412.6619

openalex publication_date 2014/12/20 · arxiv created 2015/07/04 · arxiv updated 2015/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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(nlog k) 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.

Related

• A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
• Shortest polygonal chains covering each planar square grid
• Guarding Terrains with Guards on a Line
• Robust Non-Parametric Data Approximation of Pointsets via Data Reduction
• Contracting a Planar Graph Efficiently