More Like this

1. 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
2. Lower Envelopes of Surface Patches in 3-Space

   https://doi.org/10.4230/LIPICS.ESA.2024.6  

   Agarwal, Pankaj K; Ezra, Esther; Sharir, Micha (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)

   Let Σ be a collection of n surface patches, each being the graph of a partially defined semi-algebraic function of constant description complexity, and assume that any triple of them intersect in at most s = 2 points. We show that the complexity of the lower envelope of the surfaces in Σ is O(n² log^{6+ε} n), for any ε > 0. This almost settles a long-standing open problem posed by Halperin and Sharir, thirty years ago, who showed the nearly-optimal albeit weaker bound of O(n²⋅ 2^{c√{log n}}) on the complexity of the lower envelope, where c > 0 is some constant. Our approach is fairly simple and is based on hierarchical cuttings and gradations, as well as a simple charging scheme. We extend our analysis to the case s > 2, under a "favorable cross section" assumption, in which case we show that the bound on the complexity of the lower envelope is O(n² log^{11+ε} n), for any ε > 0. Incorporating these bounds with the randomized incremental construction algorithms of Boissonnat and Dobrindt, we obtain efficient constructions of lower envelopes of surface patches with the above properties, whose overall expected running time is O(n² polylog), as well as efficient data structures that support point location queries in their minimization diagrams in O(log²n) expected time. 

   more » « less
3. Convex Polygon Containment: Improving Quadratic to Near Linear Time

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

   Chan, Timothy M; Hair, Isaac M (June 2024, Proc. 40th Sympos. Computational Geometry (SoCG))

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

   We revisit a standard polygon containment problem: given a convex k-gon P and a convex n-gon Q in the plane, find a placement of P inside Q under translation and rotation (if it exists), or more generally, find the largest copy of P inside Q under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required Ω(n²) time, even in the simplest k = 3 case. We present a significantly faster new algorithm for k = 3 achieving O(n polylog n) running time. Moreover, we extend the result for general k, achieving O(k^O(1/ε) n^{1+ε}) running time for any ε > 0. Along the way, we also prove a new O(k^O(1) n polylog n) bound on the number of similar copies of P inside Q that have 4 vertices of P in contact with the boundary of Q (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998). 

   more » « less
4. Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

   Agarwal, Pankaj K; Aronov, Boris; Ezra, Esther; Katz, Matthew J; Sharir, Micha (January 2022, Proceedings of the 38th Annual Symposium on Computational Geometry)

   Let T be a set of n planar semi-algebraic regions in R^3 of constant complexity (e.g., triangles, disks), which we call _plates_. We wish to preprocess T into a data structure so that for a query object gamma, which is also a plate, we can quickly answer various intersection queries, such as detecting whether gamma intersects any plate of T, reporting all the plates intersected by gamma, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in R^3 (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in R^3. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if T is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^(4/3)) storage (where the O^*(...) notation hides subpolynomial factors) and answers an intersection query in O^*(n^(2/3)) time. Alternatively, by increasing the storage to O^*(n^(3/2)), the query time can be decreased to O^*(n^(rho)), where rho = (2t-3)/(3(t-1)) < 2/3 and t≤3 is the number of parameters needed to represent the query arcs. 

   more » « less
5. Approximate shortest paths and distance oracles in weighted unit-disk graphs

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

   Chan, Timothy M.; Skrepetos, Dimitrios (January 2019, Journal of computational geometry)

   We present the first near-linear-time algorithm that computes a (1+ε)-approximation of the diameter of a weighted unit-disk graph of n vertices. Our algorithm requires O(n log^2 n) time for any constant ε>0, so we considerably improve upon the near-O(n^{3/2})-time algorithm of Gao and Zhang (2005). Using similar ideas we develop (1+ε)-approximate \emph{distance oracles} of O(1) query time with a likewise improvement in the preprocessing time, specifically from near O(n^{3/2}) to O(n log^3 n). We also obtain similar new results for a number of related problems in the weighted unit-disk graph metric such as the radius and the bichromatic closest pair. As a further application we employ our distance oracle, along with additional ideas, to solve the (1+ε)-approximate \emph{all-pairs bounded-leg shortest paths\/} (apBLSP) problem for a set of n planar points. Our data structure requires O(n^2 log n) space, O(loglog n) query time, and nearly O(n^{2.579}) preprocessing time for any constant ε>0, and is the first that breaks the near-cubic preprocessing time bound given by Roditty and Segal (2011). 

   more » « less