Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- Stephen R. Tate, Professor and Department Head (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
Abstract: In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O (log n) bits), then we can compute the closest pair in O (n log log n) time. We also apply our spatial decomposition technique to the k-nearest neighbor and n-body problems, achieving similar improvements.
To make use of the limited precision of the input points, we use a reasonable machine model that allows "bit shifting" in constant time—we believe that this model is realistic, and provides an interesting way of beating the Ω(n log n) lower bound that exists for this problem using the more typical algebraic RAM model.
Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input
PDF (Portable Document Format)
650 KB
Created on 3/11/2011
Views: 1054
Additional Information
- Publication
- Algorithmica, Vol. 28, 2000, pp. 271–287.
- Language: English
- Date: 2000
- Keywords
- Spatial decomposition, Computational geometry, Closest pair, n-Body problem.