A high performance graphics algorithm / North, Michael J., 1994 | Governors State University

Rendering images of complex collections of general objects in multidimensional space is typically very time consuming. The process of displaying such images is often a linear function of the number [of] objects being considered. This behavior can become unacceptable when the number of objects to be considered is large. This thesis describes an algorithm to address this problem. The graphics algorithm presented here is composed of a storage algorithm and a selection algorithm. Both of these components are described in relation to a specialized tree data structure. The storage algorithm is proven to exhibit O(n log n) average time behavior and the selection algorithm is proven to exhibit O(log n) average time behavior. This thesis focuses on two dimensional images but natural extensions of the basic algorithms to higher dimensional spaces are also considered.