Output-Sensitive Tools for Range Searching in Higher Dimensions

Micha Sharir, Shai Zaban

Let $P$ be a set of $n$ points in ${\mathbb{R}}^d$. A point $p\in P$ is $k$\emph{-shallow} if it lies in a halfspace which contains at most $k$ points of $P$ (including $p$). We…