Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage

Tal Kaminker, Micha Sharir

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. T…