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 $n$ arbitrary line segments in optimal $O(n\log 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.
This is published in _Information Processing Letters_. [#dllu]
:: IPL paper http://dx.doi.org/10.1016/j.ipl.2015.07.004
:: arXiv version http://arxiv.org/abs/1412.6619
???
???
* [#dllu] Lu, Daniel. "Planar lower envelope of monotone polygonal chains." _Information Processing Letters_ [doi:10.1016/j.ipl.2015.07.004](http://dx.doi.org/10.1016/j.ipl.2015.07.004)
???
???