Output-Sensitive Hidden Surface Elimination for Rectangles
Mikhail J. Atallah, Michael T. Goodrich · 1988
We present an algorithm for the well-known hidden-surface elimination problem for rectangles, which is also known as the window rendering problem. The time complexity of our algorithm is sensitive to the size of the output. Specifically, it runs in time that is O(n1mS + k), where k is the size of the output (which can be as large as 0(n’)). For values of k in the range between n’s6 / log n and n², our algorithm is asymptotically faster than previous ones.