@inproceedings{ad2a933b0c6940a0a9215f37e8b50953,

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",

}