A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields

ABSTRACT

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

REFERENCES

• 1: ~AARSETH, S. J., GOTr, J. R., III, AND TURNER, E. L. 1979. N-body simulations of galaxy ~clustering. I. Initial conditions and galaxy collapse times. Astrophys. J. 228, 664-683.
• 2: K. Abrahamson , N. Dadoun , D. G. Kirkpatrick , T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, v.10 n.2, p.287-302, June 1989 [doi>10.1016/0196-6774(89)90017-5]
• 3: ~ABRAMSON, N. 1963. Information Theory and Coding. McGraw-Hill, New York.
• 4: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
• 5: Pankaj K. Agarwal , Jiří Mataušek, Relative neighborhood graphs in three dimensions, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.58-65, September 1992, Orlando, Florida, United States
• 6: ~APPEL, A. W. 1985. An efficient program for many-body simulation. SIAM J. Sci. Star. Comput. ~6, 85-103.
• 7: ~BARNES, J., AND HUT, P. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature ~~ 324, 4, 446-449.
• 8: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 9: Paul B. Callahan , S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.546-556, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129766]
• 10: R. Cole , M. T. Goodrich, Optimal parallel algorithms for polygon and point-set problems, Proceedings of the fourth annual symposium on Computational geometry, p.201-210, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73414]
• 11: ~COLE, R., AND GOODRICH, M. T. 1992. Optimal parallel algorithms for point-set and polygon ~problems. Algorithmica 7, 3-23.
• 12: Alan M. Frieze , Gary L. Miller , Shang-Hua Teng, Separator based parallel divide and conquer in computational geometry, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.420-429, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141934]
• 13: ~OAZIT, H., MILLER, O. L., AND TENG, S.-H. 1988. Optimal tree contraction in the EREW model. ~In Concurrent Computations, S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz, eds. Plenum ~Publishing, New York, pp. 139-155.
• 14: ~GREENGARD, L. F. 1988. The Rapid Evaluation of Potential Ftelds in Particle Systems. The MIT ~Press, Cambridge, Mass.
• 15: ~GREENGARD, L., AND GROPP, W. D. 1990. A parallel version of the fast multipole method ~Computers Math. Applic. 20, 7, 63-71.
• 16: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 17: ~HAFNER, C., AND mUSTER, N. 1991. Computations of electromagnetic fields by the multiple ~multipole method (generalized multipole technique). Radio Sci. 26, 1, 291-297.
• 18: Jacob Katzenelson, Computational structure of the N-body problem, SIAM Journal on Scientific and Statistical Computing, v.10 n.4, p.787-815, July 1989 [doi>10.1137/0910048]
• 19: S. R. Kosaraju , A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• 20: Gary L. Miller , Shang-Hua Teng , Stephen A. Vavasis, A unified geometric approach to graph separators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.538-547, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185417]
• 21: ~MILLER, R. H., AND PRENDERGAST, K. H. 1968. Stellar dynamics in a discrete phase space ~Astrophys. J. 151, 699-709.
• 22: ~MILLER, R. H., PRENDERGAST, K. H. AND QUIRK, W. J. 1970. Numerical experiments on spiral ~structure. Astrophys. J. 161, 903 916.
• 23: ~PAN, V. Y., REIF, J. H., AND TATE, S. R. 1992. The power of combining the techniques oJ ~algebraic and numerical computing: Improved approximate multipoint polynomial evaluation ~and improved multipole algorithms. In Proceedings of the 32nd Annual Symposium of Founda- ~ttons of Computer Science. IEEE New York, pp. 703-7t3.
• 24: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 25: ~REIF, J. H., AND TARE, S. R. 1992. N-body simulation I: Potential field evaluation. Technical ~report, Comput. Sci. Dept., Duke Univ.
• 26: ~ROKHL1N, V. 1985. Rapid solution of integral equations of classical potential theory. J. Compu- ~tat. Phys. 60, 187-207.
• 27: ~SCHMIDT, K. E., AND LEE, M. m. 1991. Implementing the fast multipole method in three ~dimensions. J. Star. Phys. 63 5-6 (June), 1223-1235.
• 28: ~VAIDYA, P. M. 1986. An optimal algorithm for the all-nearest-neighbors problem. In Proceedin&, ~of the 27th Annual Sympostum Foundations of Computer Science. IEEE, New York, pp. 117-122
• 29: P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]
• 30: ~YAO, A. C. 1982. On constructing minimum spanning trees in k-dimensional space and related ~problems. SIAM J. Comput. 11,721-736.
• 31: Feng Zhao , S. Lennart Johnsson, The parallel multipole method on the connection machine, SIAM Journal on Scientific and Statistical Computing, v.12 n.6, p.1420-1437, Nov. 1991 [doi>10.1137/0912077]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Theory

Keywords:
all nearest neighbors, fast multipole method