More Like this

1. 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
2. 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
3. Eulerian Graph Sparsification by Effective Resistance Decomposition

   Jambulapati, Arun; Sachdeva, Sushant; Sidford, Aaron; Tian, Kevin; Zhao, Yibin (August 2024, https://doi.org/10.48550/arXiv.2408.10172)

   The authors present an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an 𝑂 ~ ( 𝑛 log ⁡ 2 𝑛 ⋅ 𝜀 − 2 ) O ~ (nlog 2 n⋅ε −2 )-edge 𝜀 ε-approximate Eulerian sparsifier with high probability in 𝑂 ~ ( 𝑚 log ⁡ 3 𝑛 ) O ~ (mlog 3 n) time (where 𝑂 ~ ( ⋅ ) O ~ (⋅) hides polyloglog(n) factors). By a reduction from Peng-Song (STOC ’22), this yields an 𝑂 ~ ( 𝑚 log ⁡ 3 𝑛 + 𝑛 log ⁡ 6 𝑛 ) O ~ (mlog 3 n+nlog 6 n)-time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially bounded weights with high probability, improving on the previous state-of-the-art runtime of Ω ( 𝑚 log ⁡ 8 𝑛 + 𝑛 log ⁡ 23 𝑛 ) Ω(mlog 8 n+nlog 23 n). They also provide a polynomial-time algorithm that computes sparsifiers with 𝑂 ( min ⁡ ( 𝑛 log ⁡ 𝑛 ⋅ 𝜀 − 2 + 𝑛 log ⁡ 5 / 3 𝑛 ⋅ 𝜀 − 4 / 3 , 𝑛 log ⁡ 3 / 2 𝑛 ⋅ 𝜀 − 2 ) ) O(min(nlogn⋅ε −2 +nlog 5/3 n⋅ε −4/3 ,nlog 3/2 n⋅ε −2 )) edges, improving the previous best bounds. Furthermore, they extend their techniques to yield the first 𝑂 ( 𝑚 ⋅ polylog ( 𝑛 ) ) O(m⋅polylog(n))-time algorithm for computing 𝑂 ( 𝑛 𝜀 − 1 ⋅ polylog ( 𝑛 ) ) O(nε −1 ⋅polylog(n))-edge graphical spectral sketches, along with a natural Eulerian generalization. Unlike prior approaches using short cycle or expander decompositions, their algorithms leverage a new effective resistance decomposition scheme, combined with natural sampling and electrical routing for degree balance. The analysis applies asymmetric variance bounds specialized to Eulerian Laplacians and tools from discrepancy theory. 

   more » « less
4. 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
5. Improved Algorithms for Distance Selection and Related Problems

   Wang, Haitao; Zhao, Yiming (August 2023, Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023))

   In this paper, we propose new techniques for solving geometric optimization problems involving interpoint distances of a point set in the plane. Given a set P of n points in the plane and an integer 1 ≤ k ≤ binom(n,2), the distance selection problem is to find the k-th smallest interpoint distance among all pairs of points of P. The previously best deterministic algorithm solves the problem in O(n^{4/3} log² n) time [Katz and Sharir, 1997]. In this paper, we improve their algorithm to O(n^{4/3} log n) time. Using similar techniques, we also give improved algorithms on both the two-sided and the one-sided discrete Fréchet distance with shortcuts problem for two point sets in the plane. For the two-sided problem (resp., one-sided problem), we improve the previous work [Avraham, Filtser, Kaplan, Katz, and Sharir, 2015] by a factor of roughly log²(m+n) (resp., (m+n)^ε), where m and n are the sizes of the two input point sets, respectively. Other problems whose solutions can be improved by our techniques include the reverse shortest path problems for unit-disk graphs. Our techniques are quite general and we believe they will find many other applications in future. 

   more » « less