Finding the largest disk containing a query point in logarithmic time with linear storage

Tal Kaminker, Micha Sharir

Abstract


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:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v6i2a2

ISSN: 1920-180X