Kenneth L. Clarkson
ABSTRACT
This paper gives an algorithm for approximately solving the post office problem: given n points (called sites) in d dimensions, build a data structure so that, given a query point q, a closest site to q can be found quickly. The algorithm is also given a relative error bound ε, and depends on a ratio ρ, which is no more than the ratio of the distance between the farthest pair of sites to the distance between the closest pair of sites. The algorithm builds a data structure of size O(nη)O(1/ε)(d−1)/2 in time O(n2η)O(1/ε)(d−1). Here η=log(ρ/ε). With this data structure, a site is returned whose distance to a query point q is within 1+ε of the distance of the closest site. A query needs O(logn)O(1/ε)(d−1)/2 time, with high probability.
- AM93.S. Arya and D. M. Mount. Approximate nearest neighbor queries in fixed dimensions. In Proc. Jth A CM-$IAM $ympos. Discrete Algorithms, pages 271-280, 1993. Google Scholar
Digital Library
- AMN+94.S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and Angela Wu. An optimal algorithm for approximate nearest neighbor searching. In Proc. 5~h A CM-$IAM Sympos. Discrete Algorithms, 1994. Google ScholarDigital Library
- AS90.I. Adler and R. Shamir. A randomization scheme for speeding up algorithms for linear and convex quadratic programming problems with a high constraintsto-variables ratio. Technical Report 21- 90, Rutgers Univ., May 1990. To appear in Math. Programming.Google Scholar
- Ber93.M. Bern. Approximate closest-point queries in high dimensions. Inform. Process. Lett., 45:95-99, 1993. Google ScholarDigital Library
- Cla88.K.L. Clarkson. ALas Vegas algorithm for linear programming when the dimension is small. In Proc. 29th IEEE Syrup. on Foundations of Computer Science, pages 452-456, 1988. Revised version: Las Vegas algorithms for linear and integer programming when the dimension is small (preprint).Google Scholar
- Cla93.K.L. Clarkson. Algorithms for polytope covering and approximation. In Proc. 3rd Workshop Algorithms Data Struct., Lecture Notes in Computer Science, 1993. Google ScholarDigital Library
- Dud74.R.M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approximation Theory, 10:227- 236, 1974.Google ScholarCross Ref
- Pug90.W. Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. A CM, 35:668-676, 1990. Google ScholarDigital Library
- Sen.S. Sen. Some oberservations on skip lists.Google Scholar
- Vai89.P.M. Vaidya. A new algorithm for minimizing convex functions over convex sets. In Proc. 30th Annu. IEEE $ympos. Found. Comput. Sci., pages 338-343, 1989.Google ScholarDigital Library
- Yao82.A.C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11:721-736, 1982.Google ScholarDigital Library
Index Terms
- An algorithm for approximate closest-point queries
Recommendations
New Techniques for Exact and Approximate Dynamic Closest-point
Let $S$ be a set of $n$ points in $\IR^{D}$. It is shown that a range tree can be used to find an $L_{\infty}$-nearest neighbor in $S$ of any query point, in $O((\log n)^{D-1} \log\log n)$ time. This data structure has size $O(n (\log n)^{D-1})$ ...
New techniques for exact and approximate dynamic closest-point problems
SCG '94: Proceedings of the tenth annual symposium on Computational geometryLet S be a set of n points in RD. It is shown that a range tree can be used to find an L∞ -nearest neighbor in S of any query point, in O((logn)D-1 loglogn) time. This data structure has size O(n(logn)D-1) and an amortized update time of O((logn)D-1 ...
A Dynamic Data Structure for Approximate Proximity Queries in Trajectory Data
SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsLet S be a set of n polygonal trajectories in the plane and k be a fixed constant. We present a data structure to store S so that, given a k-vertex query trajectory Q, we can answer the following queries approximately:
• Nearest neighbor query: given a ...
Comments