A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)

Full text

Pdf (1.16 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 546 - 556

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Paul B. Callahan	Computer Science Department, Johns Hopkins University, Baltimore, MD
S. Rao Kosaraju	Computer Science Department, Johns Hopkins University, Baltimore, MD

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 38, Citation Count: 18

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129712.129766 What is a DOI?

ABSTRACT

We define the notion of a well-separated pair decomposition of points in d-dimensional space. We 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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. J. Aarseth, J. it. Gott III, and E. L. Turner. N-body simulations of galaxy clustering, i. Initial conditions and galaxy collapse times. The Astrophysical Journal, 228:664-683, 1979.
	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	N. Abramson. Information Theory and Coding. McGraw-Hill, 1963.
	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	A. W. AppeL An efficient program for many-body simulation. SIAM 3. Sci. Stat. Comput., 6:85-103, 1985.
	7	J. Barnes and P. Hut. A hierarchical O(Nlog N) force-calculation algorithm. Nature, 324(4):446- 449, 1986.
	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	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]
	10	H. Gazit, G. L. Miller, and S.-H. Teng. Optimal tree contraction in the EREW model. In S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz, editors, Concurrent Computations, pages 139-155. Plenum Publishing, 1988.
	11	L. Greengard and W. D. Gropp. A parallel version of the fast multipole method. Computers Math. Applic., 20(7):63-71, 1990.
	12	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]
	13	L. F. Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. The MIT Press, 1{)88.
	14	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
	15	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]
	16	R. H. Miller and K. H. Prendergast. Stellar dynamics in a discrete phase space. The Astrophysical 3ournal, 151:699-709, 1968.
	17	R. H. Miller, K. H. Prendergast, and W. J. Quirk. Numerical experiments on spiral structure. The Astrophysical Journal, 161:903-916, 1970.
	18	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	19	J. H. Reif and S. R. Tare. The complexity of nbody simulation. (draft), Computer Science Dept., Duke University, 1992.
	20	P. M. Vaidya. A fast approximation algorithm for minimum spanning trees in k-dimensional space. In Proc. #5th Annual Syrup. Found. Comp. Sc., pages 403-407, 1984.
	21	P. M. Vaidya. An optimal algorithm for the allnearest-neighbors problem. In Proc. #Tth Annual Syrup. Found. Comp. Sc., pages 117-122, 1986.

CITED BY 18

	Sunil Arya , David M. Mount, Approximate range searching, Proceedings of the eleventh annual symposium on Computational geometry, p.172-181, June 05-07, 1995, Vancouver, British Columbia, Canada
	Marco Pellegrini, Electrostatic fields without singularities: theory and algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.184-191, January 28-30, 1996, Atlanta, Georgia, United States
	Joseph S. B. Mitchell , David M. Mount , Subhash Suri, Query-sensitive ray shooting, Proceedings of the tenth annual symposium on Computational geometry, p.359-368, June 06-08, 1994, Stony Brook, New York, United States
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
	Paul B. Callahan , S. Rao Kosaraju, Algorithms for dynamic closest pair and n-body potential fields, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.263-272, January 22-24, 1995, San Francisco, California, United States
	Dow-Yung Yang , Ananth Grama , Vivek Sarin , Naren Ramakrishnan, Compression of particle data from hierarchical approximate methods, ACM Transactions on Mathematical Software (TOMS), v.27 n.3, p.317-339, September 2001
	Sergei N. Bespamyatnikh, An optimal algorithm for closest pair maintenance (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.152-161, June 05-07, 1995, Vancouver, British Columbia, Canada
	Sunil Arya , Gautam Das , David M. Mount , Jeffrey S. Salowe , Michiel Smid, Euclidean spanners: short, thin, and lanky, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.489-498, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995
	Vivek Sarin , Ananth Grama , Ahmed Sameh, Analyzing the error bounds of multipole-based treecodes, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States
	Dow-Yung Yang , Ananth Grama , Vivek Sarin, Bounded-error compression of particle data from hierarchical approximate methods, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.71-es, November 14-19, 1999, Portland, Oregon, United States
	Dow-Yung Yang , Ananth Grama , Vivek Sarin, Bounded-error compression of particle data from hierarchical approximate methods, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.32-es, November 14-19, 1999, Portland, Oregon, United States
	Sudip Seal , Srikanth Komarina , Srinivas Aluru, An optimal hierarchical clustering algorithm for gene expression data, Information Processing Letters, v.93 n.3, p.143-147, 14 February 2005
	Richard Cole , Lee-Ad Gottlieb, Searching dynamic point sets in spaces with bounded doubling dimension, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Anil Maheshwari , Michiel Smid , Norbert Zeh, I/O-efficient algorithms for computing planar geometric spanners, Computational Geometry: Theory and Applications, v.40 n.3, p.252-271, August, 2008