Interactive explanation of my algorithm which computes the lower envelope of $m$ monotone polygonal chains with $n$ vertices in total, in $O(n + mk)$ time, where $k$ is the size of the output.

Use arrow keys to step along my algorithm. Click the diagram to play or pause the animation loop. Press esc to stop the animation entirely.

The algorithm maintains a pointer $p_1,\cdots, p_m$ on each of the $m$ chains.

When the animation is playing, blue segments are drawn between $p_i-1$ and $p_i$ and indicate the earliest segment on each chain which is neither the currently examined segment (highlighted in green), nor has been fully considered (i.e. occluded parts are proven to be occluded, and the rest are part of the output). On each iteration we increment $p_i$ until each blue segment is sticking out of the green trapezoid above the currently examined segment, either to the right or below.

The blue segments only advance if they do not stick out of the green trapezoid to the right or below, implying that any parts not previously appearing on the output are occluded by a combination of the currently and previously examined segments. A blue segment never goes back except if, during the previous iteration, it had been temporarily incremented by one because it was the then-currently examined segment. Thus the total number of increments of $p_i$ is in $O(n)$, with constant time comparisons on each incrementation. Each time a new vertex is added to the output, the algorithm loops over all $m$ polygonal chains to check for intersection with the currently examined edge and to test if the $p$ associated needs to be incremented. Since the output has $k$ vertices, this takes $O(mk)$. Thus the total run time of the algorithm is $O(n+mk)$.

To apply Chan's output sensitive algorithm [1] to lower envelopes and visibility polygons, a parameter $\kappa$ is chosen which increases to its square until it exceeds the output size $k$. On each iteration the input is divided into $\left\lceil \frac{n}{\kappa} \right\rceil$ groups of size at most $\kappa$. Hershberger's algorithm is run on each of the groups, for $O(\kappa\log\kappa)$ each ($O(n\log\kappa)$ total). Thus, in the merging step, the number of polygonal chains $m$ is $\frac{n}{\kappa}$, each of size $O(\kappa \alpha(\kappa))$ where $\alpha$ is the slow-growing inverse Ackermann function. If we force our algorithm to terminate once the output size exceeds $\kappa$, then the time complexity is in $O(n \alpha(\kappa))$. This outperforms the method proposed by Chan that uses complex data structures to merge the lower envelope with ray-shooting operations in $O\left(n\log\kappa\right)$ [1]. Our method is similar to the linear search technique E. Welzl suggested in Idea 5 of Chan's paper. Although this does not affect the $O(n\log k)$ asymptotic time complexity of the entire output-sensitive algorithm, the simplicity of our algorithm should yield a constant factor of improvement, as well as be easier to implement.

[1] Chan, Timothy M. "Optimal output-sensitive convex hull algorithms in two and three dimensions." Discrete & Computational Geometry 16.4 (1996): 361-368.