Summary: In a typical range-emptiness searching (resp., reporting) problem, we are given a set \(P\) of \(n\) points in \(\mathbb{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 \(\mathbb{R}^d\) of constant description complexity, and we wish to determine whether \(P\cap\sigma=\emptyset\), or to report all the points in \(P\cap\sigma\). Range-emptiness searching and reporting arise in many applications and have been treated by J. Matoušek [Comput. Geom. 2, No. 3, 169–186 (1992; Zbl 0772.68105)] in the special case where the ranges are half-spaces bounded by hyperplanes. As shown in Matoušek’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 Matoušek’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 \(\mathbb{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(\varepsilon)n^{\gamma+\varepsilon}\), which holds for any \(\varepsilon>0\), where \(C(\varepsilon)\) is a constant that depends on \(\varepsilon\)) 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 \(\mathbb{R}^3\) into a data structure with \(O(n)\) storage, so that, for any query line \(\ell\) (or, for that matter, any simply shaped convex set), the point of \(P\) farthest from \(\ell\) 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 \(\mathbb{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\cap P\) is empty. Alternatively, we can report, in \(O^*(1)+O(k)\) time, the points of \(\Delta\cap P\), where \(k=|\Delta\cap P|\). (iv) An algorithm that preprocesses, in \(O^*(n)\) time, a set \(P\) of \(n\) points in \(\mathbb{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\cap P\) is empty, or report the \(k\) points in \(c\cap P\) in \(O^*(1)+O(k)\) time.
Adapting the recent techniques from [B. Aronov and S. Har-Peled, ibid. 38, No. 3, 899–921 (2008; Zbl 1180.68278); B. Aronov, S. Har-Peled and the first author, in: Proceedings of the 23rd annual symposium on computational geometry 2007. NY: Association for Computing Machinery (ACM). 327–336 (2007; Zbl 1221.51026); B. Aronov and the first author, ibid. 39, No. 7, 2704–2725 (2010; Zbl 1216.68079)], 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 complements of) these structures yield faster range-emptiness searching or reporting algorithms.