TY - JOUR
AB - Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in C+q can be retrieved efficiently. If constant time sumces for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and O(k + log n) time for a query with output size k. If C is a disk, the problem becomes the wellknown fixed-radius neighbour problem, to which we thus provide the first known optimal solution.
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
ID - 4120
IS - 1
JF - Journal of Symbolic Computation
SN - 0747-7171
TI - Optimal solutions for a class of point retrieval problems
VL - 1
ER -