Worst-case optimal hidden-surface removal

Publisher Website
Google Scholar
Abstract
An O(n2) hidden-surface removal algorithm is shown. This is an improvement over the previous best worst-case performance of O(n2 log n). It has been established that the hidden-line and hidden-surface problems have an &OHgr;(n2) 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(n2) time, and (2) the portion of a 3-D polyhedron visible from a given interior point is constructible in optimal O(n2) time.

This publication has 7 references indexed in Scilit: