Unit-Disk Range Searching and Applications

Abstract

Given a set P of n points in the plane, we consider the problem of computing the number of points of P in a query unit disk (i.e., all query disks have the same radius). We show that the main techniques for simplex range searching can be adapted to this problem. For example, by adapting Matoušek’s results, we can build a data structure of O(n) space so that each query can be answered in O(√n) time; alternatively, we can build a data structure of O(n²/log² n) space with O(log n) query time. Our techniques lead to improvements for several other classical problems in computational geometry.  
1) Given a set of n unit disks and a set of n points in the plane, the batched unit-disk range counting problem is to compute for each disk the number of points in it. Previous work [Katz and Sharir, 1997] solved the problem in O(n^{4/3}log n) time. We give a new algorithm of O(n^{4/3}) time, which is optimal as it matches an Ω(n^{4/3})-time lower bound. For small χ, where χ is the number of pairs of unit disks that intersect, we further improve the algorithm to O(n^{2/3}χ^{1/3}+n^{1+δ}) time, for any δ > 0.
2) The above result immediately leads to an O(n^{4/3}) time optimal algorithm for counting the intersecting pairs of circles for a set of n unit circles in the plane. The previous best algorithms solve the problem in O(n^{4/3}log n) deterministic time [Katz and Sharir, 1997] or in O(n^{4/3}log^{2/3} n) expected time by a randomized algorithm [Agarwal, Pellegrini, and Sharir, 1993].
3) Given a set P of n points in the plane and an integer k, the distance selection problem is to find the k-th smallest distance among all pairwise distances of P. The problem can be solved in O(n^{4/3}log² n) deterministic time [Katz and Sharir, 1997] or in O(nlog n+n^{2/3}k^{1/3}log^{5/3}n) expected time by a randomized algorithm [Chan, 2001]. Our new randomized algorithm runs in O(nlog n +n^{2/3}k^{1/3}log n) expected time.
4) Given a set P of n points in the plane, the discrete 2-center problem is to compute two smallest congruent disks whose centers are in P and whose union covers P. An O(n^{4/3}log⁵ n)-time algorithm was known [Agarwal, Sharir, and Welzl, 1998]. Our techniques yield a deterministic algorithm of O(n^{4/3}log^{10/3} n⋅ (log log n)^{O(1)}) time and a randomized algorithm of O(n^{4/3}log³ n⋅ (log log n)^{1/3}) expected time.