ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Optimal Expected-Time Algorithms for Closest Point Problems
Full text PdfPdf (1.24 MB)
Source ACM Transactions on Mathematical Software (TOMS) archive
Volume 6 ,  Issue 4  (December 1980) table of contents
Pages: 563 - 580  
Year of Publication: 1980
ISSN:0098-3500
Authors
Jon Louis Bentley
Bruce W. Weide
Andrew C. Yao  Stanford University
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 18,   Downloads (12 Months): 113,   Citation Count: 57
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/355921.355927
What is a DOI?

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
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]
 
3
BENTLEY, J L., AND FRIEDMAN, J.H. Fast algorithms for constructing mmtmal spannmg trees in coordinate spaces IEEE Trans. Comput C-27, 2 (Feb. 1978), 97-105.
4
Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979  [doi>10.1145/356789.356797]
 
5
CHERITON, D, AND TARJAN, R E. Finding minimum spanning trees SIAM J. Comput. 5, 4 (Dec 1976), 724-742
 
6
DOBKIN, D, AND LIPTON, l~ J Multidimensional searching problems. SIAM J. Comput 5, 2 (June 1976), 181-186.
 
7
FORTUNE, S., AND HOPCROFT, J E A note on Rabm's nearest-neighbor algorithm. Inf. Process. Lett. 8, 1 (Jan. 1979), 20-23.
8
Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977  [doi>10.1145/355744.355745]
 
9
HORSPOOL, R N. Constructing the Voronol chagram in the plhne Tech Rep SOCS-79.12, Comput Sci School, McGill Umv, Montreal, Canada, July 1979.
 
10
KIRKPATRICK, D G Efficmnt computation of continuous skeletons. Proc. 20th IEEE Syrup Foundatmns of Computer Sctence, Oct. 1979, pp 18-27.
 
11
LIPTON, R.J., AND TARJAN, R.E. Application of a planar separator theorem. Proc 18th IEEE Symp. Foundatmns of Computer Science, Oct. 1977, pp. 162-170.
 
12
MONIER, L. Personal commumcatlon of Lores Morner of the Umversit6 de Parls-Sud to J.L. Bentley, June 1978.
13
F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977  [doi>10.1145/359423.359430]
 
14
RABIN, M O. Probabilistic algorithms, m Algorithms and Complextty: New Dwectmns and Recent Results, J.F. Traub (Ed.), Academm Press, New York, 1976, pp. 21-39.
 
15
ROHLF, F J A probabfllStlC mmnnum spannmg tree algorithm. Inf. Process. Lett. 7, 1 (Jan 1978), 44-48.
 
16
Michael Ian Shamos, Computational geometry., 1978
 
17
SHAMOS, M.I, AND HOEY, D. Closest-point problems Proc 16th IEEE Symp. Foundatmns of Computer Scwnce, Oct 1975, pp. 151-162.
 
18
Bruce Warren Weide, Statistical methods in algorithm design and analysis., 1978
 
19
YAO, A.C. An O({E{log logl V{) algorithm for findmg mmnnum spanning trees. Inf. Process. Lett. 4, 1 (Sept 1975), 21-23
 
20
Andrew C Yao, On constructing minimum spanning trees in k-dimensional spaces and related problems, Stanford University, Stanford, CA, 1977
 
21
YUVAL, G. Finding nearest neighbors. Inf. Process. Lett 5, 3 (Aug. 1976), 63-65

CITED BY  57
Peter Su , Robert L. Scot Drysdale, A comparison of sequential Delaunay triangulation algorithms, Proceedings of the eleventh annual symposium on Computational geometry, p.61-70, June 05-07, 1995, Vancouver, British Columbia, Canada
Philip D. MacKenzie , Quentin F. Stout, Ultra-fast expected time parallel algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.414-423, January 28-30, 1991, San Francisco, California, United States
A. Belussi , E. Bertino , B. Catania, Using spatial data access structures for filtering nearest neighbor queries, Data & Knowledge Engineering, v.40 n.1, p.1-31, January 2002
Mordecai J. Golin , Hyeon-Suk Na, On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, Computational Geometry: Theory and Applications, v.25 n.3, p.197-231, July 2003
Kenneth L. Clarkson, Fast expected-time and approximation algorithms for geometric minimum spanning trees, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.342-348, December 1984
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
Edith Cohen , David D. Lewis, Approximating matrix multiplication for pattern recognition tasks, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.682-691, January 05-07, 1997, New Orleans, Louisiana, United States
Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001
Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990
Jon L. Bentley , Kenneth L. Clarkson , David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.179-187, January 22-24, 1990, San Francisco, California, United States
Gary A. Hyslop , Edmund A. Lamagna, Error free incremental construction of Voronoi diagrams in the plane, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.388-396, February 14-16, 1993, Indianapolis, Indiana, United States
Robert J. Renka, Multivariate interpolation of large sets of scattered data, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.139-148, June 1988
A. El-Hamdouchi , P. Willett, Hierarchic document classification using Ward's clustering method, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.149-156, September 1986, Palazzo dei Congressi, Pisa, Italy
Y. T. Lee , A. Pennington , N. K. Shaw, Automatic finite-element mesh generation from geometric models—A point-based approach, ACM Transactions on Graphics (TOG), v.3 n.4, p.287-311, Oct. 1984
F. Cazals , C. Puech, Bucket-like space partitioning data structures with applications to ray-tracing, Proceedings of the thirteenth annual symposium on Computational geometry, p.11-20, June 04-06, 1997, Nice, France
Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
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
Oscar Palacios-Velez, A dynamic hierarchical subdivision algorithm for computing Delaunay triangulations and other closest-point problems, ACM Transactions on Mathematical Software (TOMS), v.16 n.3, p.275-291, Sept. 1990
Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States
Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
R A Dwyer, A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time, Proceedings of the second annual symposium on Computational geometry, p.276-284, June 02-04, 1986, Yorktown Heights, 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
S Fortune, A sweepline algorithm for Voronoi diagrams, Proceedings of the second annual symposium on Computational geometry, p.313-322, June 02-04, 1986, Yorktown Heights, New York, United States
Giri Narasimhan , Martin Zachariasen, Geometric Minimum Spanning Trees via Well-Separated Pair Decompositions, Journal of Experimental Algorithmics (JEA), 6, p.6-es, 2001
A. Faragó , T. Linder , G. Lugosi, Fast Nearest-Neighbor Search in Dissimilarity Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.957-962, September 1993
Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984
Helmut Alt , Laura Heinrich-Litan, Exact L∞ nearest neighbor search in high dimensions, Proceedings of the seventeenth annual symposium on Computational geometry, p.157-163, June 2001, Medford, Massachusetts, United States
Markku Tamminen, Efficient spatial access to a data base, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997
Luc Devroye , Christophe Lemaire , Jean-Michel Moreau, Expected time analysis for Delaunay point location, Computational Geometry: Theory and Applications, v.29 n.2, p.61-89, October 2004
A. M. Roumani , D. B. Skillicorn, Mobile services discovery and selection in the publish/subscribe paradigm, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.163-173, October 04-07, 2004, Markham, Ontario, Canada
Fionn Murtagh, Comments on 'Parallel Algorithms for Hierarchical Clustering and Cluster Validity', IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.10, p.1056-1057, October 1992
Apostolos N. Papadopoulos , Yannis Manolopoulos, Distributed Processing of Similarity Queries, Distributed and Parallel Databases, v.9 n.1, p.67-92, January 1, 2001
King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
Mineichi Kudo , Naoto Masuyama , Jun Toyama , Masaru Shimbo, Simple termination conditions for k-nearest neighbor method, Pattern Recognition Letters, v.24 n.9-10, p.1203-1213, 01 June 2003
Adam Runions , Martin Fuhrer , Brendan Lane , Pavol Federl , Anne-Gaëlle Rolland-Lagan , Przemyslaw Prusinkiewicz, Modeling and visualization of leaf venation patterns, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
B. C. Vemuri , R. Varadarajan , N. Mayya, An efficient expected time parallel algorithm for Voronoi construction, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.392-401, June 29-July 01, 1992, San Diego, California, United States
Vincent C. H. Ma , Michael D. McCool, Low latency photon mapping using block hashing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
Markku Tamminen , Reijo Sulonen, The excell method for efficient geometric access to data, Proceedings of the 19th conference on Design automation, p.345-351, January 1982
Peter Klier , Richard J. Fateman, On finding the closest bitwise matches in a fixed set, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.88-97, March 1991
Prosenjit Bose , Luc Devroye, On the stabbing number of a random Delaunay triangulation, Computational Geometry: Theory and Applications, v.36 n.2, p.89-105, February, 2007
Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China
Sanghamitra Bandyopadhyay , Sriparna Saha, GAPS: A clustering method using a new point symmetry-based distance measure, Pattern Recognition, v.40 n.12, p.3430-3451, December, 2007
J. D. Boissonnat, Reconstruction of solids, Proceedings of the first annual symposium on Computational geometry, p.46-54, June 05-07, 1985, Baltimore, Maryland, United States
M. T. Fang , Richard C. T. Lee , C. C. Chang, The Idea of De-Clustering and its Applications, Proceedings of the 12th International Conference on Very Large Data Bases, p.181-188, August 25-28, 1986
Jonathan Goldstein , Raghu Ramakrishnan, Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches, Proceedings of the 26th International Conference on Very Large Data Bases, p.429-440, September 10-14, 2000
Jiyeong Lee, A Spatial Access-Oriented Implementation of a 3-D GIS Topological Data Model for Urban Entities, Geoinformatica, v.8 n.3, p.237-264, September 2004
Guy Tsafnat, The Field Representation Language, Journal of Biomedical Informatics, v.41 n.1, p.46-57, February, 2008
Sameer A. Nene , Shree K. Nayar, A Simple Algorithm for Nearest Neighbor Search in High Dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.9, p.989-1003, September 1997
Mirko Zadravec , Andrej Brodnik , Markus Mannila , Merja Wanne , Borut alik, A practical approach to the 2D incremental nearest-point problem suitable for different point distributions, Pattern Recognition, v.41 n.2, p.646-653, February, 2008
Wojciech Jarosz , Henrik Wann Jensen , Craig Donner, Advanced global illumination using photon mapping, ACM SIGGRAPH 2008 classes, August 11-15, 2008, Los Angeles, California
Jean-Charles Créput , Abderrafiãa Koukam, A memetic neural network for the Euclidean traveling salesman problem, Neurocomputing, v.72 n.4-6, p.1250-1264, January, 2009
Sriparna Saha , Sanghamitra Bandyopadhyay, Some Symmetry Based Classifiers, Fundamenta Informaticae, v.90 n.1-2, p.107-123, February 2009
Sang Wook Yang , Young Choi , Hyun Chan Lee, CAD data visualization on mobile devices using sequential constrained Delaunay triangulation, Computer-Aided Design, v.41 n.5, p.375-384, May, 2009
Sriparna Saha , Sanghamitra Bandyopadhyay, A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters, Information Sciences: an International Journal, v.179 n.19, p.3230-3246, September, 2009

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS


General Terms:
Algorithms, Theory

Collaborative Colleagues:
Jon Louis Bentley: colleagues
Bruce W. Weide: colleagues
Andrew C. Yao: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player