@inproceedings{f83c73364b4a4829975a83a6aff05ae8,
title = "Optimal solutions for a class of point retrieval problems",
abstract = "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 fized radius neighbor problem, to which we thus provide the first known optimal solution.",
author = "Bernard Chazelle and Herbert Edelsbrunner",
note = "Publisher Copyright: {\textcopyright} 1985, Springer-Verlag.; 12th International Colloquium on Automata, Languages and Programming, ALP 1985 ; Conference date: 15-07-1985 Through 19-07-1985",
year = "1985",
doi = "10.1007/BFb0015733",
language = "English (US)",
isbn = "9783540156505",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "80--89",
editor = "Wilfried Brauer",
booktitle = "Automata, Languages and Programming - 12th Colloquium",
address = "Germany",
}