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∩σ)=∑p∈P∩σw(p) for every σ∈Σ in overall expected time O∗(m2s5s-4n5s-65s-4+m2/3n2/3+m+n), where s>0 is the number of degrees of freedom 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∗(ms2s-1n2s-22s-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 (edge-disjoint) bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) O∗(m2s5s-4n5s-65s-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, in the same asymptotic time bound. A recent work of Chan et al. [28] solves the on-line version of this dual point enclosure problem within the same performance bound as our off-line solution.

Duke Scholars

Author Pankaj K. Agarwal Computer Science