Worst-case optimal hidden-surface removal
Michael S. McKenna · ACM Transactions on Graphics · 1987
An O( n 2 ) hidden-surface removal algorithm is shown. This is an improvement over the previous best worst-case performance of O( n 2 log n ). It has been established that the hidden-line and hidden-surface problems have an Ω( n 2 ) worst-case lower bound, so the algorithm is optimal. However, the algorithm is not output-size sensitive. Two corollaries to the result are (1) hidden-lines can be removed in optimal O( n 2 ) time, and (2) the portion of a 3-D polyhedron visible from a given interior point is constructible in optimal O( n 2 ) time.