More Like this

1. On the Line-Separable Unit-Disk Coverage and Related Problems

   https://doi.org/10.4230/LIPIcs.ISAAC.2023.51  

   Liu, Gang ; Wang, Haitao ( November 2023 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Iwata, Satoru ; Kakimura, Naonori (Ed.)

   Given a set P of n points and a set S of m disks in the plane, the disk coverage problem asks for a smallest subset of disks that together cover all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line 𝓁. We present an m^{2/3} n^{2/3} 2^O(log^*(m+n)) + O((n+m)log(n+m)) time algorithm for the problem. This improves the previously best result of O(nm + n log n) time. Our techniques also solve the line-constrained version of the problem, where centers of all disks of S are located on a line 𝓁 while points of P can be anywhere in the plane. Our algorithm runs in O(m√n + (n+m)log(n+m)) time, which improves the previously best result of O(nm log(m+n)) time. In addition, our results lead to an algorithm of n^{10/3} 2^O(log^*n) time for a half-plane coverage problem (given n half-planes and n points, find a smallest subset of half-planes covering all points); this improves the previously best algorithm of O(n⁴log n) time. Further, if all half-planes are lower ones, our algorithm runs in n^{4/3} 2^O(log^*n) time while the previously best algorithm takes O(n²log n) time. 

   more » « less
2. Algorithms for Halfplane Coverage and Related Problems

   https://doi.org/10.4230/LIPIcs.SoCG.2024.79  

   Wang, Haitao ; Xue, Jie ( June 2024 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)

   Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an O(n^{4/3}log^{5/3}nlog^{O(1)}log n)-time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of n^{10/3}2^{O(log^*n)} time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O(nlog n) time, which improves the previously best algorithm of n^{4/3}2^{O(log^*n)} time and matches an Ω(nlog n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O(nlog n) time, which in turn leads to an O(nlog n)-time algorithm for computing an instance-optimal ε-kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O(nklog n)-time algorithm for this problem in SoCG 2023, where k is the size of the ε-kernel; they also raised an open question whether the problem can be solved in O(nlog n) time. Our result thus answers the open question affirmatively. 

   more » « less
3. Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems

   https://doi.org/10.4230/LIPIcs.MFCS.2024.68  

   Liu, Gang ; Wang, Haitao ( August 2024 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kráľovič, Rastislav ; Kučera, Antonín (Ed.)

   Given a set P of n points and a set S of m disks in the plane, the disk hitting set problem asks for a smallest subset of P such that every disk of S contains at least one point in the subset. The problem is NP-hard. This paper considers a line-constrained version in which all disks have their centers on a line. We present an O(mlog²n+(n+m)log(n+m)) time algorithm for the problem. This improves the previous result of O(m²log m+(n+m)log(n+m)) time for the weighted case of the problem where every point of P has a weight and the objective is to minimize the total weight of the hitting set. Our algorithm also solves a more general line-separable problem with a single intersection property: The points of P and the disk centers are separated by a line 𝓁 and the boundary of every two disks intersect at most once on the side of 𝓁 containing P. 

   more » « less
4. Unit-disk range searching and applications

   https://doi.org/10.20382/jocg.v14i1a13  

   Wang, Haitao ( December 2023 , Journal of computational geometry)

   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 in the plane can be adapted to this problem. For example, by adapting Matoušek's results, we can build a data structure of $O(n)$ space in $O(n^{1+\delta})$ time (for any $\delta>0$) so that each query can be answered in $O(\sqrt{n})$ time; alternatively, we can build a data structure of $O(n^2/\log^2 n)$ space with $O(n^{1+\delta})$ preprocessing time (for any $\delta>0$) and $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 $\Omega(n^{4/3})$-time lower bound. For small $\chi$, where $\chi$ is the number of pairs of unit disks that intersect, we further improve the algorithm to $O(n^{2/3}\chi^{1/3}+n^{1+\delta})$ time, for any $\delta>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^2 n)$ deterministic time [Katz and Sharir, 1997] or in $O(n\log 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(n\log 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^5 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\cdot (\log\log n)^{O(1)})$ time and a randomized algorithm of $O(n^{4/3}\log^3 n\cdot (\log\log n)^{1/3})$ expected time. 

   more » « less
5. Geometric Hitting Set for Line-Constrained Disks

   https://doi.org/10.1007/978-3-031-38906-1_38  

   Liu, Gang ; Wang, Haitao ( August 2023 , Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023))

   Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset 𝑃′ of points of P such that each disk contains at least one point of 𝑃′ and the total weight of all points of 𝑃′ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line ℓ. We present an 𝑂((𝑚+𝑛)log(𝑚+𝑛)+𝜅log𝑚) time algorithm for the problem, where 𝜅 is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to 𝑂((𝑛+𝑚)log(𝑚+𝑛)). In addition, we solve the problem in 𝑂((𝑚+𝑛)log(𝑚+𝑛)) time in the 𝐿∞ and 𝐿1 metrics, in which a disk is a square and a diamond, respectively. 

   more » « less