Divide-and-conquer in multidimensional space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Divide-and-conquer in multidimensional space

Full text

Pdf (620 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighth annual ACM symposium on Theory of computing table of contents

Hershey, Pennsylvania, United States

Pages: 220 - 230

Year of Publication: 1976

Authors

Jon Louis Bentley
Michael Ian Shamos

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 96, Citation Count: 22

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/800113.803652 What is a DOI?

ABSTRACT

We investigate a divide-and-conquer technique in multidimensional space which decomposes a geometric problem on N points in k dimensions into two problems on N/2 points in k dimensions plus a single problem on N points in k−1 dimension. Special structure of the subproblems is exploited to obtain an algorithm for finding the two closest of N points in 0(N log N) time in any dimension. Related results are discussed, along with some conjectures and unsolved geometric problems.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Bentley, J. L. and Friedman, J. Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces. SLAC Technical Report.
	3	Blum, M., et al. "Time Bounds for Selection." JCSS 7 (1973), 448-461.
	4	H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
	5	Preparata, F. P. and Hong, S. J. Convex Hulls of Finite Planar and Spatial Sets of Points. Report R-682, Coordinated Science Laboratory, University of Illinois (April, 1975).
	6	Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
	7	Shamos, M. I. "Geometry and Statistics: Problems at the Interface." Proc. Symposium on Algorithms and Complexity, Carnegie-Mellon University. April, 1975.
	8	Shamos, M. I. "Problems in Computational Geometry." Unpublished manuscript.
	9	Shamos, M. I. and Hoey, D. J. "Closest-Point Problems." Proc. 16th Annual Symposium on Foundations of Computer Science. October, 1975.
	10	Strong, H. R. Private communication.

CITED BY 22

	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
	George Nagy , Sharad Wagle, Geographic Data Processing, ACM Computing Surveys (CSUR), v.11 n.2, p.139-181, June 1979
	Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
	Mordecai Golin , Rajeev Raman , Christian Schwarz , Michiel Smid, Randomized data structures for the dynamic closest-pair problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.301-310, January 25-27, 1993, Austin, Texas, United States
	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
	Jon Louis Bentley, K-d trees for semidynamic point sets, Proceedings of the sixth annual symposium on Computational geometry, p.187-197, June 07-09, 1990, Berkley, California, United States
	Christian Schwarz , Michiel Smid , Jack Snoeyink, An optimal algorithm for the on-line closest-pair problem, Proceedings of the eighth annual symposium on Computational geometry, p.330-336, June 10-12, 1992, Berlin, Germany
	Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980
	Christian Schwarz , Michiel Smid, An Onlognloglogn algorithm for the on-line closest pair problem, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.280-285, September 1992, Orlando, Florida, United States
	N. S. V. Rao , E. M. Oblow , C. W. Glover, Learning Separations by Boolean Combinations of Half-Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.7, p.765-768, July 1994
	David Dobkin , Subhash Suri, Maintenance of geometric extrema ∈ , Journal of the ACM (JACM), v.38 n.2, p.275-298, April 1991
	Timothy M. Chan, On enumerating and selecting distances, Proceedings of the fourteenth annual symposium on Computational geometry, p.279-286, June 07-10, 1998, Minneapolis, Minnesota, United States
	Jon Louis Bentley , Dorothea Haken , James B. Saxe, A general method for solving divide-and-conquer recurrences, ACM SIGACT News, v.12 n.3, Fall 1980
	Mordecai Golin , Rajeev Raman , Christian Schwarz , Michiel Smid, Simple randomized algorithms for closest pair problems, Nordic Journal of Computing, v.2 n.1, p.3-27, March 1995
	Fabrizio Angiulli , Clara Pizzuti, An approximate algorithm for top-k closest pairs join query in large high dimensional data, Data & Knowledge Engineering, v.53 n.3, p.263-281, June 2005
	Prosenjit Bose , Anil Maheshwari , Pat Morin , Jason Morrison , Michiel Smid , Jan Vahrenhold, Space-efficient geometric divide-and-conquer algorithms, Computational Geometry: Theory and Applications, v.37 n.3, p.209-227, August, 2007
	Bernard Chazelle, New techniques for computing order statistics in Euclidean space (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.125-134, June 05-07, 1985, Baltimore, Maryland, United States
	Pankaj K. Agarwal , Haim Kaplan , Micha Sharir, Kinetic and dynamic data structures for closest pair and all nearest neighbors, ACM Transactions on Algorithms (TALG), v.5 n.1, p.1-37, November 2008
	Gyozo Gidofalvi , Torben Bach Pedersen , Tore Risch , Erik Zeitler, Highly scalable trip grouping for large-scale collective transportation systems, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Raymond Chi-Wing Wong , Yufei Tao , Ada Wai-Chee Fu , Xiaokui Xiao, On efficient spatial matching, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Minghui Jiang , Joel Gillespie, Engineering the divide-and-conquer closest pair algorithm, Journal of Computer Science and Technology, v.22 n.4, p.532-540, July 2007
	Chin-Chen Chang , Yung-Chen Chou , Chih-Yang Lin, Reversible Data Hiding in the VQ-Compressed Domain, IEICE - Transactions on Information and Systems, v.E90-D n.9, p.1422-1429, September 2007