Let P be a set of m points in \({\mathbb R}^2\) , let \(\Sigma \) be a set of n semi-algebraic sets of constant complexity in \({\mathbb R}^2\) , let \((S,+)\) be a semigroup, and let \(w: P \rightarrow S\) be a weight function on the points of P. We describe a randomized algorithm for computing \(w(P\cap \sigma ) = \sum _{p\in P\cap \sigma } w(p)\) for every \(\sigma \in \Sigma \) in overall expected time \(O^*\bigl ( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr )\) , where \(s>0\) is the number of degrees of freedom of the regions of \(\Sigma \) , and where the \(O^*(\cdot )\) notation hides subpolynomial factors. For \(s\ge 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^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}+m+n)\) time. Let \(\Phi : \Sigma \times P \rightarrow \{0,1\}\) be the Boolean predicate (of constant complexity) such that \(\Phi (\sigma ,p) = 1\) if \(p\in \sigma \) and 0 otherwise, and let \(\Sigma \mathop {\Phi } P = \{ (\sigma ,p) \in \Sigma \times P \mid \Phi (\sigma ,p)=1\}\) . Our algorithm actually computes a partition \(\mathscr {B}_\Phi \) of \(\Sigma \mathop {\Phi } P\) into (edge-disjoint) bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) \(O^*\bigl ( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr )\) . It is straightforward to compute \(w(P\cap \sigma )\) for all \(\sigma \in \Sigma \) from \(\mathscr {B}_\Phi \) . Similarly, if \(\eta : \Sigma \rightarrow S\) is a weight function on the regions of \(\Sigma \) , \(\sum _{\sigma \in \Sigma : p \in \sigma } \eta (\sigma )\) , for every point \(p\in P\) , can be computed from \(\mathscr {B}_\Phi \) 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.
