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

Full Text:



ISSN: 1920-180X