SEMIALGEBRAIC RANGE REPORTING AND EMPTINESS SEARCHING WITH APPLICATIONS
In a typical range-emptiness searching (resp., reporting) problem, we are given a set P of n points in R(d), and we wish to preprocess it into a data structure that supports efficient range-emptiness (resp., reporting) queries, in which we specify a range sigma, which, in general, is a semialgebraic set in R(d) of constant description complexity, and we wish to determine whether P boolean AND sigma = phi, or to report all the points in P boolean AND sigma. Range-emptiness searching and reporting arise in many applications and have been treated by Matousek [Comput. Geom. Theory Appl., 2 (1992), pp. 169-186] in the special case where the ranges are half-spaces bounded by hyperplanes. As shown in Matousek's work, the two problems are closely related, and they have solutions (for the case of half-spaces) with similar performance bounds. In this paper we extend the analysis to general semialgebraic ranges and show how to adapt Matousek's technique without the need to linearize the ranges into a higher-dimensional space. This yields more efficient solutions to several useful problems, and we demonstrate the new technique in four applications with the following results: (i) An algorithm for ray shooting amid balls in R(3), which uses O(n) storage and O*(n) preprocessing (we use the notation O*(n(gamma)) to mean an upper bound of the form C(epsilon)n(gamma+epsilon), which holds for any epsilon > 0, where C(epsilon) is a constant that depends on epsilon) and answers a query in O*(n(2/3)) time, improving the previous bound of O*(n(3/4)). (ii) An algorithm that preprocesses, in O*(n) time, a set P of n points in R(3) into a data structure with O(n) storage, so that, for any query line l (or, for that matter, any simply shaped convex set), the point of P farthest from l can be computed in O*(n(1/2)) time. This in turn yields an algorithm that computes the largest-area triangle spanned by P in time O*(n(26/11)), as well as nontrivial algorithms for computing the largest-perimeter or largest-height triangle spanned by P. (iii) An algorithm that preprocesses, in O*(n) time, a set P of n points in R(2) into a data structure with O(n) storage, so that, for any query alpha-fat triangle Delta, we can determine, in O*(1) time, whether Delta boolean AND P is empty. Alternatively, we can report, in O*(1) + O(k) time, the points of Delta boolean AND P, where k - vertical bar Delta boolean AND P|. (iv) An algorithm that preprocesses, in O*(n) time, a set P of n points in R(2) into a data structure with O(n) storage, so that, given any query semidisk c, or a circular cap larger than a semidisk, we can determine, in O*(1) time, whether c boolean AND P is empty, or report the k points in c boolean AND P in O*(1) + O(k) time. Adapting the recent techniques of [B. Aronov and S. Har-Peled, SIAM J. Comput., 38 (2008), pp. 899-921, B. Aronov, S. Har-Peled, and M. Sharir, On approximate halfspace range counting and relative epsilon-approximations, in Proceedings of the 23rd ACM Symposium Comput. Geom., 2007, pp. 327-336, B. Aronov and M. Sharir, SIAM J. Comput., 39 (2010), pp. 2704-2725], we can turn our solutions into efficient algorithms for approximate range counting (with small relative error) for the cases mentioned above. 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 (decompositions of complemens of) these structures yield faster range-emptiness searching or reporting algorithms.
range reporting semialgebraic sets ray shooting range searching range emptiness random sampling elementary cell partition epsilon nets