Lower bounds on the complexity of polytope range searching
Bernard Chazelle · Journal of the American Mathematical Society · 1989
Orthogonal range searching and simplex range searching have received much attention recently in the computational geometry literature. Whereas the former problem is nearing a definitive solution, however, the complexity of simplex range searching has long remained elusive. To state the problem simply, suppose that we are given n points in Euclidean d-space, fixed once and for all, and m units of computer memory. We wish to organize the memory to be in a position to answer the following type of queries efficiently: Given an arbitrary simplex q, how many of the n points lie inside q ? A natural variant of the problem calls for reporting the points in question and not simply counting them. More generally, it is customary to weight the points ahead of time and then ask for the cumulative weight of the subset of points that fall within the query. There is abundant practical application to motivate research on this problem [5, 6, 7, 10, 11, 15, 18, 20, 22]. For example, clipping and removing hidden surfaces in computer graphics are fundamental tasks whose computational bottlenecks are instances of simplex range searching. Also of great interest is the central theoretical question lying underneath: What is the most efficient way of organizing information to support a given class of queries? What takes this question apart from the classical problem of searching a linear list is the power of redundancy. While oversupply of memory space is usually of marginal interest when searching a linear list, it is often the key to efficiency in multidimensional searching. For this reason, the principal research activity in that area has been the investigation of space-time trade-offs. Our main result is a family of lower bounds on the space-time complexity of simplex range searching. We prove that the worst case query time is Q(n/l/Hi) in the Euclidean plane, and more generally, Q((n/ log n)/m'l/d) in d-space, for d > 3, where n is the number of points and m is the amount of storage available. l These bounds hold with high probability for a random point-set