Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane

Let P be a set of m points in R2, let Σ be a set of n semi-algebraic sets of constant complexity in R2, 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 2s time O∗(m5s−4 n5 5 s s − − 6 4 + m2/3n2/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 2s−2 s on-line manner. The latter takes O∗(m2s−1 n2s−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 BΦ of Σ Φ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes 2s of the vertex sets of its bicliques) O∗(m5s−4 n5 5 s s − − 4 6 + m2/3n2/3 + m + n). It is straightforward to compute w(P ∩ σ) for all σ ∈ Σ from BΦ. Similarly, if η : Σ → S is a weight function on the regions of Σ, Pσ∈Σ:p∈σ η(σ), for every point p ∈ P, can be computed from BΦ in a straightforward manner. We also mention a few other applications of computing BΦ

Duke Scholars

Author Pankaj K. Agarwal Computer Science