An algorithm for generalized point location and its applications

We show that Collins' classical quantifier elimination procedure contains most of the ingredients for an efficient point location algorithm in higher-dimensional space. This leads to a polynomial-size data structure that allows us to locate, in logarithmic time, a point among a collection of real algebraic varieties of constant maximum degree, assuming that the dimension of the ambient space is fixed. This result has theoretical bearings on a number of optimization problems posed in the literature. It also gives a method for solving multidimensional searching problems in polynomial space and logarithmic query time.