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

Let P be a set of m points in R², let Σ be a set of n semi-algebraic sets of constant complexity in R², 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^*( m2s/5s-4n5s-6/5s-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 on-line manner. The latter takes O^*(ms/2s-1n2s-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 B_Φ of ΣΦ P into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O^*( m2s/5s-4n5s-6/5s-4 + 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 ∈ σ η(σ), for every point p∈ P, can be computed from B_Φ in a straightforward manner. A recent work of Chan et al. solves the online version of this dual point enclosure problem within the same performance bound as our off-line solution. We also mention a few other applications of computing B_Φ.