Output-Sensitive Methods for Rectilinear Hidden Surface Removal

AbstractWe present an algorithm for the hidden-surface elimination problem for rectangles, which is also known as window rendering. The time complexity of our algorithm is dependent on both the number of input rectangles, n, and on the size of the output, k. Our algorithm obtains a trade-off between these two components, in that its running time is O(r(n1+1/r + k)), where 1 ≤ r ≤ log n is a tunable parameter. By using this method while adjusting the parameter r "on the fly" one can achieve a running time that is O(n log n + k(log n/log(1+k/n))). Note that when k is Θ(n), this achieves an O(n log n) running time, and when k is Θ(n1+ϵ) for any positive constant ϵ, this achieves an O(k) running time, both of which are optimal