Lower envelope of monotone polygonal chains

2014-12-20

Computing the lower envelope of monotone polygonal chains is important in visibility problems in robotics, facility location, video games, architecture, and so on. 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(n\log k)$ time, where 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.

This is published in Information Processing Letters. dllu

IPL paper

arXiv version

dllu Lu, Daniel. “Planar lower envelope of monotone polygonal chains.” Information Processing Letters doi:10.1016/j.ipl.2015.07.004