skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

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


Title: Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane
Let P be a set of m points in ℝ², let Σ be a set of n semi-algebraic sets of constant complexity in ℝ², let (S,+) be a semigroup, and let w: P → S be a weight function on the points of P. We describe a randomized algorithm for computing w(P∩σ) for every σ ∈ Σ in overall expected time O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n), where s > 0 is a constant that bounds the maximum complexity of the regions of Σ, and where the O^*(⋅) notation hides subpolynomial factors. For s ≥ 3, surprisingly, this bound is smaller than the best-known bound for answering m such queries in an on-line manner. The latter takes O^*(m^{s/(2s-1)}n^{(2s-2)/(2s-1)} + m + n) time. Let Φ: Σ × P → {0,1} be the Boolean predicate (of constant complexity) such that Φ(σ,p) = 1 if p ∈ σ and 0 otherwise, and let Σ_Φ P = {(σ,p) ∈ Σ× P ∣ Φ(σ,p) = 1}. Our algorithm actually computes a partition ℬ_Φ of Σ_Φ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O^*(m^{2s/(5s-4)}n^{(5s-6)/(5s-4)} + m^{2/3}n^{2/3} + m + n). It is straightforward to compute w(P∩σ) for all σ ∈ Σ from ℬ_Φ. Similarly, if η: Σ → S is a weight function on the regions of Σ, ∑_{σ ∈ Σ: p ∈ σ} η(σ), for every point p ∈ P, can be computed from ℬ_Φ in a straightforward manner. We also mention a few other applications of computing ℬ_Φ.  more » « less
Award ID(s):
2007556 2223870
PAR ID:
10548216
Author(s) / Creator(s):
; ;
Editor(s):
Mulzer, Wolfgang; Phillips, Jeff M
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
293
ISSN:
1868-8969
ISBN:
978-3-95977-316-4
Page Range / eLocation ID:
293-293
Subject(s) / Keyword(s):
Range-searching semi-algebraic sets pseudo-lines duality geometric cuttings Theory of computation
Format(s):
Medium: X Size: 15 pages; 804403 bytes Other: application/pdf
Size(s):
15 pages 804403 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Morin, Pat; Oh, Eunjin (Ed.)
    Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known. 
    more » « less
  2. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mulzer, Wolfgang; Phillips, Jeff M (Ed.)
    Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of ℝ² and let 𝒟 = {D_1,…,D_n} be a set of geodesic disks with respect to the metric d. We prove that 𝒢^×(𝒟), the intersection graph of the disks in 𝒟, has a clique-based separator consisting of O(n^{3/4+ε}) cliques. This significantly extends the class of objects whose intersection graphs have small clique-based separators. Our clique-based separator yields an algorithm for q-Coloring that runs in time 2^O(n^{3/4+ε}), assuming the boundaries of the disks D_i can be computed in polynomial time. We also use our clique-based separator to obtain a simple, efficient, and almost exact distance oracle for intersection graphs of geodesic disks. Our distance oracle uses O(n^{7/4+ε}) storage and can report the hop distance between any two nodes in 𝒢^×(𝒟) in O(n^{3/4+ε}) time, up to an additive error of one. So far, distance oracles with an additive error of one that use subquadratic storage and sublinear query time were not known for such general graph classes. 
    more » « less
  3. ; ; (, 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
  4. ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)
    In this paper we study a few proximity problems related to a set of pairwise-disjoint segments in {ℝ}². Let S be a set of n pairwise-disjoint segments in {ℝ}², and let r > 0 be a parameter. We define the segment proximity graph of S to be G_r(S) := (S,E), where E = {(e₁,e₂) ∣ dist(e₁,e₂) ≤ r} and dist (e₁,e₂) = min_{(p,q) ∈ e₁× e₂} ‖p-q‖ is the Euclidean distance between e₁ and e₂. We define the weight of an edge (e₁,e₂) ∈ E to be dist(e₁,e₂). We first present a simple grid-based O(nlog² n)-time algorithm for computing a BFS tree of G_r(S). We apply it to obtain an O^*(n^{6/5}) + O(nlog²nlogΔ)-time algorithm for the so-called reverse shortest path problem, in which we want to find the smallest value r^* for which G_{r^*}(S) contains a path of some specified length between two designated start and target segments (where the O^*(⋅) notation hides polylogarithmic factors). Here Δ = max_{e ≠ e' ∈ S} dist(e,e')/min_{e ≠ e' ∈ S} dist(e,e') is the spread of S. Next, we present a dynamic data structure that can maintain a set S of pairwise-disjoint segments in the plane under insertions/deletions, so that, for a query segment e from an unknown set Q of pairwise-disjoint segments, such that e does not intersect any segment in (the current version of) S, the segment of S closest to e can be computed in O(log⁵ n) amortized time. The amortized update time is also O(log⁵ n). We note that if the segments in S∪Q are allowed to intersect then the known lower bounds on halfplane range searching suggest that a sequence of n updates and queries may take at least close to Ω(n^{4/3}) time. One thus has to strongly rely on the non-intersecting property of S and Q to perform updates and queries in O(polylog(n)) (amortized) time each. Using these results on nearest-neighbor (NN) searching for disjoint segments, we show that a DFS tree (or forest) of G_r(S) can be computed in O^*(n) time. We also obtain an O^*(n)-time algorithm for constructing a minimum spanning tree of G_r(S). Finally, we present an O^*(n^{4/3})-time algorithm for computing a single-source shortest-path tree in G_r(S). This is the only result that does not exploit the disjointness of the input segments. 
    more » « less
  5. ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Chan, Timothy; Fischer, Johannes; Iacono, John; Herman, Grzegorz (Ed.)
    We study the problem of robust multivariate polynomial regression: let p: ℝⁿ → ℝ be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (𝐱_i,y_i) ∈ [-1,1]ⁿ × ℝ that are noisy versions of (𝐱_i,p(𝐱_i)). More precisely, each 𝐱_i is sampled independently from some distribution χ on [-1,1]ⁿ, and for each i independently, y_i is arbitrary (i.e., an outlier) with probability at most ρ < 1/2, and otherwise satisfies |y_i-p(𝐱_i)| ≤ σ. The goal is to output a polynomial p̂, of degree at most d in each variable, within an 𝓁_∞-distance of at most O(σ) from p. Kane, Karmalkar, and Price [FOCS'17] solved this problem for n = 1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of O_n(dⁿlog d), where the hidden constant depends on n, if χ is the n-dimensional Chebyshev distribution. The sample complexity is O_n(d^{2n}log d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O(σ), and the run-time depends on log(1/σ). In the setting where each 𝐱_i and y_i are known up to N bits of precision, the run-time’s dependence on N is linear. We also show that our sample complexities are optimal in terms of dⁿ. Furthermore, we show that it is possible to have the run-time be independent of 1/σ, at the cost of a higher sample complexity. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email