---
_id: '4120'
abstract:
- lang: eng
text: '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.'
acknowledgement: The first author was supported i~1 part by NSF grants MCS 83-03925
and the Office of Naval Research and the Defense Advanced Research Projects Agency
under contract N00014-g3-K-0146 and ARPA Order No. 4786.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 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
apa: Chazelle, B., & Edelsbrunner, H. (1985). Optimal solutions for a class
of point retrieval problems. Journal of Symbolic Computation. Elsevier.
https://doi.org/10.1016/S0747-7171(85)80028-6
chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “Optimal Solutions for a Class
of Point Retrieval Problems.” Journal of Symbolic Computation. Elsevier,
1985. https://doi.org/10.1016/S0747-7171(85)80028-6.
ieee: B. Chazelle and H. Edelsbrunner, “Optimal solutions for a class of point retrieval
problems,” Journal of Symbolic Computation, vol. 1, no. 1. Elsevier, pp.
47–56, 1985.
ista: Chazelle B, Edelsbrunner H. 1985. Optimal solutions for a class of point retrieval
problems. Journal of Symbolic Computation. 1(1), 47–56.
mla: 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.
short: B. Chazelle, H. Edelsbrunner, Journal of Symbolic Computation 1 (1985) 47–56.
date_created: 2018-12-11T12:07:03Z
date_published: 1985-03-01T00:00:00Z
date_updated: 2022-01-31T09:20:18Z
day: '01'
doi: 10.1016/S0747-7171(85)80028-6
extern: '1'
intvolume: ' 1'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.sciencedirect.com/science/article/pii/S0747717185800286?via%3Dihub
month: '03'
oa: 1
oa_version: Published Version
page: 47 - 56
publication: Journal of Symbolic Computation
publication_identifier:
eissn:
- 1095-855X
issn:
- 0747-7171
publication_status: published
publisher: Elsevier
publist_id: '2004'
quality_controlled: '1'
status: public
title: Optimal solutions for a class of point retrieval problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1985'
...