Finding the maximal empty disk containing a query point
Haim Y. Kaplan, Micha Sharir · 2012
Let P be a set of n points in the plane. We present an efficient algorithm for preprocessing P, so that, for a given query point q, we can quickly report the largest disk that contains q but its interior is disjoint from P. The storage required by the data structure is O(n log n), the preprocessing cost is O(n log2n), and a query takes O(log2n) time.