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 -