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

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

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…