Ray shooting amid balls, farthest point from a line, and range emptiness searching

摘要

In the range emptiness searching problem, we are given a set P of n points in R^d, and wish to preprocess them into a data structure that supports efficient range emptiness queries, in which we specify a range σ, which is a semi-algebraic set in R^d of some fixed kind, and wish to determine whether P ∩ σ = θ. Range emptiness searching arises in many applications, and has been treated by Matousek [15] in the special case where the ranges are halfspaces bounded by hyperplanes. In this paper we extend the analysis to the general semi-algebraic case, and show how to adapt Matousek's technique to this case, without the need to linearize the ranges into a higher-dimensional space. This yields more efficient solutions to several interesting problems, and we demonstrate the new technique in two applications:(i) An algorithm for ray shooting amid balls in R³, which uses O* (n) storage and preprocessing, and answers a query in O* (n^2/3) time, improving the previous bound of O* (n^3/47).(ii) An algorithm that preprocesses, in O*(n) time, a set P of n points in R³ into a data structure with O*(n) storage, so that, for any query line l or segment e, the point of P farthest from l or from e can be computed in O* (n^1/2) time.Our technique is closely related to the notions of nearest- or farthest-neighbor generalized Voronoi diagrams, and of the union or intersection of geometric objects, where sharper bounds on the combinatorial complexity of these structures yield faster range emptiness searching algorithms. For example, in the case of ray shooting amid balls, the structure that arises in our algorithm is the Euclidean Voronoi diagram of lines in 3-space, and the performance of the algorithm depends on the complexity of such diagrams (for which tight bounds arestill unknown).