Orthogonal Emptiness Queries for Random Points

Jonathan E. Dullerud, Sariel Har-Peled

We present a data-structure for orthogonal range searching for random points in the plane. The new data-structure uses (in expectation) $O(n\log n(\log \log n{)}^2)$ sp…