Sanjiv Kapoor
ABSTRACT
Let 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 loglogn). This result is used to solve the (1+ ϵ)-approximate L2-nearest neighbor problem within the same bounds. In this problem, for any query point p, a point ∈ is computed such that the euclidean distance between p and q is at most (1+ϵ) times the euclidean distance between p and its true nearest neighbor. This is the first dynamic data structure for this problem having close to linear size and polylogarithmic query and update times.
New dynamic data structures are given that maintain a closest pair of S. For D ≥ 3, a structure of size O(n) is presented with amortized update time O((logn)D- loglogn). For D = 2 and any non-negative integer constant k, structures of size O(nlogn/(loglogn)k) (resp. O(n)) are presented having an amortized update time of O(lognloglogn) (resp. O((logn)2/(loglogn)k)). Previously, no deterministic linear size data structure having polylogarithmic update time was known for this problem.
- 1.S. Arya and D.M. Mount. Approximate nearest neighbor queries in fixed dimensions. Proc. SODA 1993, 271-280. Google Scholar
Digital Library
- 2.S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, A. Wu. An optimal algorithm for approximate nearest neighbor searching. Proc. SODA 1994, pp. 573-582. Google ScholarDigital Library
- 3.K.L. Clarkson. A randomized algorithm for closest-point queries. SIAM J. Comput. 17 (19ss), s30-s47. Google ScholarDigital Library
- 4.H. Edelsbrunner, G. Haring and D. Hilbert. Rectangular point location in d dimensions with applications. The Computer Journal 29 9s6), 76-s2.Google ScholarCross Ref
- 5.M. Golin, R. Raman, C. Schwarz and M. Staid. Randomized data structures for the dynamic closest-pair problem. Proc. SODA 1993, 301- 310. Google ScholarDigital Library
- 6.K. Mehlhorn and S. N'~er. Dynamic fractional cascading. Algorithmica 5 (1990), 215- 241.Google ScholarDigital Library
- 7.F.P. Preparata and M.I. Shamos. Computational Geometry, an introduction. Springer- Verlag, New York, 1985. Google ScholarDigital Library
- 8.J.S. Salowe. Shallow interdistance selection and interdistance enumeration. International Journal of Computational Geometry & Applications 2 (1992), 49-59.Google Scholar
- 9.C. Schwarz. Data structures and algorithms for the dynamic closest pair problem. Ph.D. Thesis. Universit~it des Saarlandes, Saarbrficken, 1993.Google Scholar
- 10.C. Schwarz, M. Staid and J. Snoeyink. An optimal algorithm for the on-line closest pair problem. Proc. A. CM Syrup. on Computational Geometry, 1992, 330-336. Google ScholarDigital Library
- 11.M. Staid. Rectangular point location and the dynamic closest pair problem. Proc. 2nd Annual International Syrup. on Algorithms, Lecture Notes in Computer Science, Vol. 557, Springer-Verlag, Berlin, 1991, 364-374. Google ScholarDigital Library
- 12.M. Staid. Maintaining the minimal distance of a point set in polylogarithrnic time. Discrete Comput. Geom. 7 (1992), 415-431.Google ScholarDigital Library
- 13.K.J. Supowit. New techniques for some dynamic closest-point and farthest-point problems. Proc. SODA 1990, 84-90. Google ScholarDigital Library
- 14.P.M. Vaidya. An O(n log n) algorithm for the all-nearest-neighbors problem. Discrete Cornput. Geom. 4 (1989), 101-115.Google ScholarDigital Library
- 15.A.C. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11 (1982), 721-736.Google ScholarDigital Library
Index Terms
- New techniques for exact and approximate dynamic closest-point problems
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})$ ...
Euclidean minimum spanning trees and bichromatic closest pairs
We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inEd in timeO(Fd(N,N) logdN), whereFd(n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inEd. IfFd(N,N)=Ω(N1+ ), ...
Sensitive functions and approximate problems
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer ScienceWe investigate properties of functions that are good measures of the CRCW PRAM complexity of computing them. While the block sensitivity is known to be a good measure of the CREW PRAM complexity, no such measure is known for CRCW PRAMs. We show that the ...
Comments