Efficient algorithm for finding spheres farthest apart in large collection
algorithm, collections, comparison, geometry
Solution
The largest distance between any two points in a set `S` of points is called the diameter. Finding the diameter of a set of points is a well-known problem in computational geometry. In general, there are two steps here:
Find the three-dimensional convex hull composed of the center of each sphere -- say, using the `quickhull` implementation in CGAL.
Find the points on the hull that are farthest apart. (Two points on the interior of the hull cannot be part of the diameter, or otherwise they would be on the hull, which is a contradiction.)
With quickhull, you can do the first step in O(n log n) in the average case and O(n2) worst-case running time. (In practice, quickhull significantly outperforms all other known algorithms.) It is possible to guarantee a better worst-case bound if you can guarantee certain properties about the ordering of the spheres, but that is a different topic.
The second step can be done in Ω(h log h), where `h` is the number of points on the hull. In the worst case, `h = n` (every point is on the hull), but that's pretty unlikely if you have thousands of random spheres. In general, `h` will be much smaller than `n`. Here's an overview of this method.
Problem
I've got a collection of 10000 - 100000 spheres, and I need to find the ones farthest apart. One simple way to do this is to simply compare all the spheres to each other and store the biggest distance, but this feels like a real resource hog of an algorithm. The Spheres are stored in the following way: ``` Sphere (float x, float y, float z, float radius); ``` The method Sphere::distanceTo(Sphere &s) returns the distance between the two center points of the spheres. Example: ``` Sphere *spheres; float biggestDistance; for (int i = 0; i < nOfSpheres; i++) { for (int j = 0; j < nOfSpheres; j++) { if (spheres[i].distanceTo(spheres[j]) > biggestDistance) { biggestDistance = spheres[i].distanceTo(spheres[j]) > biggestDistance; } } } ``` What I'm looking for is an algorithm that somehow loops through all the possible combinations in a smarter way, if there is any. The project is written in C++ (which it has to be), so any solutions that only work in languages other than C/C++ are of less interest.