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"
}