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$.
Categories: cs.CG