Orthogonal Emptiness Queries for Random Points

Abstract

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)$ space, and answers emptiness queries in constant time. As a building block, we construct a data-structure of expected linear size, that can answer predecessor/rank queries, in constant time, for random numbers sampled uniformly from $[0,1]$. While the basic idea we use is known [Dev89], we believe our results are still interesting.