Semi-algebraic Range Reporting and Emptiness Searching with Applications

Micha Sharir, Hayim Shaul

In a typical range emptiness searching (resp., reporting) problem, we are given a set $P$ of $n$ points in ${\mathbb{R}}^d$, and wish to preprocess it into a data structure that supports…