Finding the Maximal Empty Rectangle Containing a Query Point

Haim Kaplan, Micha Sharir

Let $P$ be a set of $n$ points in an axis-parallel rectangle $B$ in the plane. We present an $O(n\alpha (n){\log }^{4}n)$-time algorithm to preprocess $P$ into a data structure of size $O(nα…