Optimal solutions for a class of point retrieval problems

B. Chazelle, H. Edelsbrunner, Journal of Symbolic Computation 1 (1985) 47–56.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
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 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.
Publishing Year
Date Published
1985-03-01
Journal Title
Journal of Symbolic Computation
Volume
1
Issue
1
Page
47 - 56
IST-REx-ID

Cite this

Chazelle B, Edelsbrunner H. Optimal solutions for a class of point retrieval problems. Journal of Symbolic Computation. 1985;1(1):47-56. doi:10.1016/S0747-7171(85)80028-6
Chazelle, B., & Edelsbrunner, H. (1985). Optimal solutions for a class of point retrieval problems. Journal of Symbolic Computation, 1(1), 47–56. https://doi.org/10.1016/S0747-7171(85)80028-6
Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class of Point Retrieval Problems.” Journal of Symbolic Computation 1, no. 1 (1985): 47–56. https://doi.org/10.1016/S0747-7171(85)80028-6.
B. Chazelle and H. Edelsbrunner, “Optimal solutions for a class of point retrieval problems,” Journal of Symbolic Computation, vol. 1, no. 1, pp. 47–56, 1985.
Chazelle B, Edelsbrunner H. 1985. Optimal solutions for a class of point retrieval problems. Journal of Symbolic Computation. 1(1), 47–56.
Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class of Point Retrieval Problems.” Journal of Symbolic Computation, vol. 1, no. 1, Elsevier, 1985, pp. 47–56, doi:10.1016/S0747-7171(85)80028-6.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar