Shape sensitive geometric complexity
Y. Zhou, Subhash Suri · 2000
The traditional algorithm analysis for geometric problems has focused on worst-case asymptotic complexity. Such analyses have often concluded that certain simple algorithms are worthless because they have poor worst-case performance. However, empirical experience shows that these algorithms tend to perform very well in practice. How does one explain this disparity? This dissertation uses shape sensitive analysis to explores this phenomenon by investigating two problems: the use of bounding boxes in collision detection, and the complexity of geometric permutations in visibility computation. Bounding boxes are used widely in computer graphics as simple approximations of complex objects. Because of their simpler shape, computing with boxes is almost always easier and faster than with the original objects. Experience has shown that the use of bounding boxes greatly impr...