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. On Line-Separable Weighted Unit-Disk Coverage and Related Problems

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

   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 n weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the union of the disks in the subset covers 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 O(n^{3/2}log² n) time algorithm for the problem. This improves the previously best work of O(n²log n) time. Our result leads to an algorithm of O(n^{7/2}log² n) time for the halfplane coverage problem (i.e., using n weighted halfplanes to cover n points), an improvement over the previous O(n⁴log n) time solution. If all halfplanes are lower ones, our algorithm runs in O(n^{3/2}log² n) time, while the previous best algorithm takes O(n²log n) time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities. 

   more » « less
3. 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
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. Constructing many faces in arrangements of lines and segments

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

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

   We present new algorithms for computing many faces in arrangements of lines and segments. Given a set $S$ of $n$ lines (resp., segments) and a set $P$ of $m$ points in the plane, the problem is to compute the faces of the arrangements of $S$ that contain at least one point of $P$. For the line case, we give a deterministic algorithm of $O(m^{2/3}n^{2/3}\log^{2/3} (n/\sqrt{m})+(m+n)\log n)$ time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $\log^{2.22}n$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $\log^{1/3}n$ in certain cases (e.g., when $m=\Theta(n)$). For the segment case, we present a deterministic algorithm of $O(n^{2/3}m^{2/3}\log n+\tau(n\alpha^2(n)+n\log m+m)\log n)$ time, where $\tau=\min\{\log m,\log (n/\sqrt{m})\}$ and $\alpha(n)$ is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $\log^{2.11}n$ and improves the previously best randomized algorithm [Agarwal, Matoušek, and Schwarzkopf, 1998] by a factor of $\log n$ in certain cases (e.g., when $m=\Theta(n)$). We also give a randomized algorithm of $O(m^{2/3}K^{1/3}\log n+\tau(n\alpha(n)+n\log m+m)\log n\log K)$ expected time, where $K$ is the number of intersections of all segments of $S$. In addition, we consider the query version of the problem, that is, preprocess $S$ to compute the face of the arrangement of $S$ that contains any given query point. We present new results that improve the previous work for both the line and the segment cases. In particulary, for the line case, we build a data structure of $O(n\log n)$ space in $O(n\log n)$ randomized time, so that the face containing the query point can be obtained in $O(\sqrt{n\log n})$ time with high probability (more specifically, the query returns a binary search tree representing the face so that standard binary-search-based queries on the face can be handled in $O(\log n)$ time each and the face itself can be output explicitly in time linear in its size). 

   more » « less