Shape sensitive geometric complexity

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 improves the performance of geometric algorithms in collision detection, rendering and modeling. However, the goal of proving that bounding boxes maintain high performance in the worst case has remained elusive. In fact, traditional analysis of algorithms has concluded that in the worst-case bounding boxes add nothing but overhead. We will show how to reconcile this discrepancy using shape-sensitive analysis. Our proof shows that the performance of bounding boxes depends on two natural shape parameters of objects, and the observed efficiency of boxes can be attributed to the fact that objects in practice tend to have small values of these parameters.; The second part of this thesis focuses on the complexity of geometric permutations. Geometric permutations are a natural analog of the more familiar numerical permutation. Given a set of disjoint convex bodies in some fixed d-dimensional space, a geometric permutation is the order in which these objects can be intersected by a line. We will be interested in the “combinatorics” of such permutations—namely, given n objects in d-space, how many combinatorially distinct geometric permutations are possible. Our breakthrough result is that a set of n unit balls in $Rd$ admits at most a constant number of geometric permutations. The constant bound significantly improves upon the Θ(n d−1) bound for the balls of arbitrary radii. Intrigued by this large gap between the two bounds, we then study how the number of geometric permutations varies as a function of shape, size, and spacing of objects.