Solving query-retrieval problems by compacting Voronoi diagrams
Alok Aggarwal, Mark D. Hansen, T. Leighton · 1990
In this paper, we describe a new technique for solving a variety of query-retrieval problems in optimal time with optimal or near-optimal space.In particular, we use the technique to construct algorithms and data structures for circular range searching, half-space range searching, and computing k-nearest neighbors in a variety of metrics.For each problem and each query, the response to the query is provided in O(k) or O(k + log n) time where k is the size of the response and n is the size of the problem.(E.g., for the n-point k-nearest neighbors problem, the k-nearest neighbors of any query point are provided in O(k -4log n) steps.)Depending on the problem being solved, the space required for the data structure is either linear or O(n log n).Hence, the time bounds are optimal and the space bounds are optimal or near-optimal.Previously known data structures for these problems required a factor of ~(log n(log log n) 2) or ~(log n log log n) more space and/or more time to answer each query.Our compaction technique incorporates planar separators, filtering search, and the probabilistic method for discrepancy problems.The fundamental idea is that k'h-order Voronoi diagrams (and other suitable proximity diagrams) can be compacted from k°(1)n space to O(n) space and still retain all the information that is essential for solving query problems.This result is of independent interest and may be useful in improving the memory space requirement or the query-time bound for other query-retrieval problems.