Localized geometric query problems (Q1931281)

Let \(P\) be a collection of figures in the plane. In the maximum empty circle query problem, for each query point \(q\), one is to determine the largest disk that contains \(q\), but whose interior does not intersect \(P\). The article presents algorithms for solving this problem in the case when \(P\) is the entire plane with a single simple polygon removed (so that one searches for disks contained inside the polygon), and in the case when \(P\) is a collection of points. In the polygon case, an elaborate data structure that takes \(O(n\lg{n})\) space is constructed in \(O(n\lg^2{n})\) time, and such queries take \(O(\lg{n})\) time. In the point set case, two data structures are presented. The first structure takes \(O(n^{3/2}\lg{n})\) space and \(O(n^{3/2}\lg^2{n})\) time, and allows queries that take \(O(\lg{n}\lg\lg{n})\) time. The second takes \(O(n^{5/3})\) space and \(O(n^{5/2}\lg{n})\) time, and allows \(O(\lg{n})\) query times.