Optimal solutions for a class of point retrieval problems (Q1062772)

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 suffices 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 well-known fixed-radius neighbour problem, to which we thus provide the first known optimal solution.