AbstractWe define the notion of a well-separated pair decomposition of points in d-dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation of k-nearest neighbors and n-body potential fields. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- geometrical problems and computation; F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism and concurrency
General Terms: Algorithms, Theory
Additional Key Words and Phrases: All nearest neighbors, fast multipole method
Selected papers that cite this one
- Richard J. Anderson. Tree data structures for N-body simulation. In 37th Annual Symposium on Foundations of Computer Science, pages 224-233, Burlington, Vermont, 14-16 October 1996. IEEE.
- Guoliang Xue. An O(n) time hierarchical tree algorithm for computing force field in n-body simulations. Theoretical Computer Science, 197(1-2):157-169, 15 May 1998.
Selected references
- Paul B. Callahan and S. Rao Kosaraju. A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 546-556, Victoria, British Columbia, Canada, 4-6 May 1992.
- Gary L. Miller, Shang-Hua Teng, and Stephen A. Vavasis. A unified geometric approach to graph separators. In 32nd Annual Symposium on Foundations of Computer Science, pages 538-547, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- V. Y. Pan, J. H. Reif, and S. R. Tate. The power of combining the techiques of algebraic and numerical computing: Improved approximate multipoint polynomial evaluation and improved multipole algorithms. In 33rd Annual Symposium on Foundations of Computer Science, pages 703-713, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Pravin M. Vaidya. An optimal algorithm for the All-Nearest-Neighbors problem. In 27th Annual Symposium on Foundations of Computer Science, pages 117-122, Toronto, Ontario, Canada, 27-29 October 1986. IEEE.