Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage
Tal Kaminker, Micha Sharir · 2014
Let D be a set of n disks in the plane. We present a data structure of size O(n) that can compute, for any query point q, the largest disk in D that contains q, in O(log n) time. The structure can be constructed in O(n log3 n) time. The optimal storage and query time of the structure improve several recent results on this and related problems [1, 2, 4].