TY - JOUR

T1 - Optimal solutions for a class of point retrieval problems

AU - Chazelle, B.

AU - Edelsbrunner, H.

N1 - Funding Information:
The generality of the setting allows a uniform solution of several probiems which have been treated separately in the past. If C is a disk, the problem becomes the well-known fixed-radius neighbour problem (Bentley & Maurer, 1979; Chazelle, 1983a; Chazelle et al., 1984). The best solution to this problem achieves optimal retrieval time at the cost of O(n(log n log log n) 2) space (Chazelle et at., 1984), but also handles queries with non-fixed radius. If C is a triangle or a rectangle then we have restricted versions of the triangular and orthogonal range search problems (Knuth, 1973; Edelsbrunner et at., 1982; Chazelle, 1983b; Cole & Yap, 1983; Edelsbrunner & Welzl, 1983; Willard, 1985). Again, optimal retrieval time is achieved only with superlinear space. Other shapes which C may assume include ellipses or hybrid convex figures bounded by a constant number of analytic curves. We look at the special case where C is a convex m-gon and m is considered a 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.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022022987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022022987&partnerID=8YFLogxK

U2 - 10.1016/S0747-7171(85)80028-6

DO - 10.1016/S0747-7171(85)80028-6

M3 - Article

AN - SCOPUS:0022022987

SN - 0747-7171

VL - 1

SP - 47

EP - 56

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 1

ER -