skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Friday, December 13 until 2:00 AM ET on Saturday, December 14 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Unit-disk range searching and applications
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
Award ID(s):
2300356
PAR ID:
10546353
Author(s) / Creator(s):
Publisher / Repository:
Journal of Computational Geometry
Date Published:
Journal Name:
Journal of computational geometry
Volume:
14
Issue:
1
ISSN:
1920-180X
Format(s):
Medium: X
Right(s):
Creative Commons Attribution 4.0 International
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ( , 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. ; ( , 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
  3. ( , 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
  4. ; ( , 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
  5. ; ( , 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
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email