Searching in higher dimension

Multidimensional searching addresses search problems where the underlying universe lacks a total order. Hit detection in computer graphics, range searching in databases, point location in geographical maps are well-known instances of such problems. We will review some recent developments in that area. Point location in a nonlinear universe involves preprocessing a collection of real-algebraic varieties to facilitate the location of a query point. By using probabilistic data structuring techniques we can reduce the problem to the general question of stratifying semi-algebraic sets into simple smooth manifolds. Another subject of current interest is the manipulation of lines and segments in Euclidean 3-space. Given a set of lines one may wish to compute their upper envelope or be ready to answer questions of the form: given a new line (or a set of new lines), does it (or do they) all lie above the lines in the database? This problem has applications to ray-tracing in a polyhedral environment. Another subject with interesting recent developments is polytope range searching: the problem involves preprocessing a collection of points in rf-space so that, given a query simplex q, the number of points inside q can be evaluated efficiently. We wil report on practical solutions which offer a whole spectrum of quasi-optimal tradeoffs between storage and query time.