Abstract | ||
---|---|---|
Let P be a set of n points in the plane. We present an efficient algorithm for preprocessing P, so that, for a given query point q, we can quickly report the largest disk that contains q but its interior is disjoint from P. The storage required by the data structure is O(n log n), the preprocessing cost is O(n log2n), and a query takes O(log2n) time. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/2261250.2261292 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
maximal empty disk,data structure,n log2n,efficient algorithm,preprocessing p,largest disk,query point q,n log n,preprocessing cost,n point,data structures,algorithms,computational geometry | Discrete mathematics,Data structure,Combinatorics,Disjoint sets,Computational geometry,Preprocessor,Time complexity,Mathematics | Conference |
Citations | PageRank | References |
8 | 0.71 | 5 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Haim Kaplan | 1 | 3581 | 263.96 |
Micha Sharir | 2 | 8405 | 1183.84 |