Lower Bounds on the Complexity of Polytope Range Searching

Abstract:

Polytope range searching is a central problem in multimensional searching, with applications to computer graphics, robotics, and database design. In its most elementary form, the problem can be stated as follows: Given a collection P of n weighted points in Euclidean d-space and a simplex q, compute the cumulative weight of Pcapq: The points are given once and for all and can be preprocessed. The simplex q, however, forms a query which must be answered on-line. We assume that the weights are chosen in a commutative semigroup and that the time to answer a query includes only the number of arithmetic operations performed by the algorithm. We prove that if m units of storage are available then the worst-case query time is omega(n/sqrtm) in 2-space, and more generally,
omega((n/log n)/m1/d) in d-space, if d geq 3. These bounds also hold with high probability for a random set of points (drawn uniformly in the d-cube) and remains true if the queries are restricted to congruent copies of a fixed simplex. In the course of our investigation we also establish results of independent interest regarding a generalization of Heilbronn's problem.