From: cohenj@cs.unc.edu (Jonathan Cohen) Newsgroups: comp.graphics.algorithms Subject: Re: Fast 3D closest point algorithm wanted! Date: 14 Feb 1996 01:28:50 -0500 In article <31217A2E.4BE4@ucla.edu>, Loren McQuade wrote: >Is there any fast (less than O(n^2)) algorithm for finding the 2 closest >points out of a set of n 3D points? > >Thanks - Loren McQuade - mcquade@ucla.edu The first way that comes to mind is to generate some hierarchical space-partitioning data structure, such as an octree, containing these points. Then you can test only pairs of points that lie in the same cell or neighboring cells for their distances. This algorithm should take O(nlogn) time. If you aren't familiar with such space partitioning structures, I could elaborate a bit more... Jon ============================================================================== From: orourke@grendel.csc.smith.edu (Joseph O'Rourke) Newsgroups: comp.graphics.algorithms Subject: Re: Fast 3D closest point algorithm wanted! Date: 15 Feb 1996 11:47:45 GMT In article <31217A2E.4BE4@ucla.edu>, Loren McQuade wrote: >Is there any fast (less than O(n^2)) algorithm for finding the 2 closest >points out of a set of n 3D points? > There is a large literature on this topic. Most of it can be found by searching the computational geometry bibliography (see the FAQ) for the key term "closest-point." Here is one early paper: @article{bwy-oetac-80 , author = "J. L. Bentley and B. W. Weide and A. C. Yao" , title = "Optimal expected-time algorithms for closest-point problems" , journal = "ACM Trans. Math. Softw." , volume = 6 , year = 1980 , pages = "563--580" } ============================================================================== From: jeffe@ocarina.CS.Berkeley.EDU (Jeff Erickson) Newsgroups: comp.graphics.algorithms Subject: Re: Fast 3D closest point algorithm wanted! Date: 16 Feb 96 00:15:06 GMT Loren McQuade writes: >Is there any fast (less than O(n^2)) algorithm for finding the 2 closest >points out of a set of n 3D points? Yes. Bentley describes an algorithm (due to Bentley and Shamos) that runs in O(n log n) time. Vaidya describes an algorithm the find the nearest neighbor of every point in O(n log n) time. Both algorithms are optimal. See also my previous post on finding k nearest neighbors in the plane. @inproceedings{bs-dcms-76 , author = "J. L. Bentley and M. I. Shamos" , title = "Divide-and-conquer in multidimensional space" , booktitle = "Proc. 8th Annu. ACM Sympos. Theory Comput." , year = 1976 , pages = "220--230" } @article{b-mdc-80 , author = "J. L. Bentley" , title = "Multidimensional divide-and-conquer" , journal = "Commun. ACM" , volume = 23 , number = 4 , year = 1980 , pages = "214--229" } @article{v-oaann-89 , author = "P. M. Vaidya" , title = "An {$O(n \log n)$} algorithm for the all-nearest-neighbors problem" , journal = "Discrete Comput. Geom." , volume = 4 , year = 1989 , pages = "101--115" } -- Jeff Erickson jeffe@cs.berkeley.edu http://www.cs.berkeley.edu/~jeffe ============================================================================== Newsgroups: comp.graphics.algorithms From: clarkson@research.att.com (Ken Clarkson <8718-20110> 0112720) Subject: Re: Fast 3D closest point algorithm wanted! Date: Fri, 16 Feb 1996 19:58:51 GMT Bentley was able to show that it's possible to find the closest pair in O(n log n) time in arbitrary dimension; of course, the "constant" here depends sharply on the dimension. In one of the earliest papers on randomization in algorithms, Rabin was able to show that using random bits and the floor function, you can find the closest pair in O(n) expected time, where the expectation is over the behavior of the algorithm, and holds for any point set. I was able to show that you can find the nearest neighbors of all points in O(n log n) using a quadtree-like algorithm; my code used randomization and bit twiddling; Vaidya later gave a similar algorithm, and removed the randomization and bit-twiddling. A simpler version of my algorithm requires O(n log n) time for "reasonable" distributions of points: those for which the ratio of the farthest pair distance to the closest pair distance is polynomial in n. As to a practical method, none of these algorithms are horrible in small dimension; I'd guess that Rabin's is actually quite reasonable to implement. If you have a Delaunay triangulation code lying around, you might use that and look through the Delaunay neighbors for the closest pair. -Ken @phdthesis{b-dcacp-76 , author = "J. L. Bentley" , title = "Divide-and-conquer algorithms for closest point problems in multidimensional space" , type = "Ph.{D}. Thesis" , school = "Dept. Comput. Sci., Univ. North Carolina" , address = "Chapel Hill, NC" , year = 1976 , note = "Report TR-76-103" , keywords = "doctoral thesis" , update = "93.05 jones" } @incollection{r-pa-76 , author = "M. O. Rabin" , title = "Probabilistic algorithms" , editor = "J. F. Traub" , booktitle = "Algorithms and Complexity" , publisher = "Academic Press" , address = "New York, NY" , year = 1976 , pages = "21--30" } @inproceedings{c-faann-83 , author = "K. L. Clarkson" , title = "Fast algorithms for the all nearest neighbors problem" , booktitle = "Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci." , year = 1983 , pages = "226--232" , keywords = "proximity, bucketing, approximation, probabilistic analysis" } @article{v-oaann-89 , author = "P. M. Vaidya" , title = "An {$O(n \log n)$} algorithm for the all-nearest-neighbors problem" , journal = "Discrete Comput. Geom." , volume = 4 , year = 1989 , pages = "101--115" , succeeds = "v-oaann-86" } ============================================================================== From: orourke@grendel.csc.smith.edu (Joseph O'Rourke) Newsgroups: comp.graphics.algorithms Subject: Re: nearest points Date: 19 Feb 1996 01:11:30 GMT In article <4g304f$4c4@ncar.ucar.edu>, Fred Clare wrote: >If I have N coordinates in 2-space and a specific >coordinate P, does anyone know of an efficient algorithm >for finding the M (< N) points from the original set of N >that are closest to P? The key idea here is to compute the Voronoi diagram of N points, and then to locate the "query" point P in a cell of the diagram. There are lots of programs available for computing the Voronoi diagram in two dimensions. You could start with our FAQ, which I will email you separately. ============================================================================== From: orourke@grendel.csc.smith.edu (Joseph O'Rourke) Newsgroups: comp.graphics.algorithms Subject: Re: Fast 2D neighbor point algorithm wanted Date: 19 Feb 1996 19:15:25 GMT In article <4fvkq5$j4g@news.csie.nctu.edu.tw>, Shih-Hsu Chang wrote: >Is there any fast (less than O(n^2)) algorithm for finding the N closest >points out of a set of M 2D points? Here is one recent paper on the topic: @article{dds-saeid-92 , author = "M. T. Dickerson and R. L. Drysdale and J. R. Sack" , title = "Simple algorithms for enumerating interpoint distances and finding $k$ nearest neighbors" , journal = "Internat. J. Comput. Geom. Appl." , volume = 2 , number = 3 , year = 1992 , pages = "221--239" , keywords = "enumeration, selection, Delaunay triangulation, nearest neighbors" }