@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 = "Funding Information: The generality of the setting allows a uniform solution of several problems which have been treated separately in the past. If C is a disk, the problem becomes the well-known fized.radius neighbor problem [BM,C1,CCPY]. The best solution to this problem achieves optimal retrieval time at the cost of O(n(lognloglogn) ~) space [CCPY], but also handles queries with non-fixed radius. If G is a triangle or a rectangle then we have restricted versions of the triangular and orthogonal range search problems Authors' current address: B. Chazelle: Dept. of Computer Science, Box 1910, Brown Univ., Providence, RI 02912, USA. H. Edelsbrnamer: Last. Inf. Proc, Tectm. Univ. Graz, Schiesstattg. 4a, A-8010, Gras, Austria. The first author was supported in part by NSF grant MCS 83-03925. 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",

}