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