  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)$ 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 a constant that bounds the maximum complexity 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
${\mathcal B}_\Phi$ of $\Sigma\mathop{\Phi} P$ into 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 ${\mathcal 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 ${\mathcal B}_\Phi$ 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 ${\mathcal B}_\Phi$.
