Optimal solutions for a class of point retrieval problems Chazelle, Bernard Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 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. Elsevier 1985 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4120 Chazelle B, Edelsbrunner H. Optimal solutions for a class of point retrieval problems. <i>Journal of Symbolic Computation</i>. 1985;1(1):47-56. doi:<a href="https://doi.org/10.1016/S0747-7171(85)80028-6">10.1016/S0747-7171(85)80028-6</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/S0747-7171(85)80028-6 info:eu-repo/semantics/altIdentifier/issn/0747-7171 info:eu-repo/semantics/altIdentifier/e-issn/1095-855X info:eu-repo/semantics/openAccess