Efficient algorithm for finding spheres farthest apart in large collection

Question

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.

Answer 1

Could you perhaps store these spheres in a BSP Tree? If that's acceptable, then you could start by looking for nodes of the tree containing spheres which are furthest apart. Then you can continue down the tree until you get to individual spheres.

Answer 2

Your problem looks like something that could be solved using graphs. Since the distance from Sphere A to Sphere B is the same as the distance from Sphere B to Sphere A, you can minimize the number of comparisons you have to make.

I think what you're looking at here is known as an Adjacency List. You can either build one up, and then traverse that to find the longest distance.

Another approach you can use will still give you an O(n^2) but you can minimize the number of comparisons you have to make. You can store the result of your calculation into a hash table where the key is the name of the edge (so AB would hold the length from A to B). Before you perform your distance calculation, check to see if AB or BA exists in the hash table.

EDIT

Using the adjacency-list method (which is basically a Breadth-First Search) you get O(b^d) or worst-case O(|E| + |V|) complexity.

Answer 3

Paul got my brain thinking and you can optimize a bit by changing

for (int j=0; j < nOfSpheres; j++) 

to

for (int j=i+1;  j < nOfSpheres; j++) 

You don't need to compare sphere A to B AND B to A. This will make the search O(n log n).

--- Addition -------

Another thing that makes this calculation expensive is the DistanceTo calulations.

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)

That's alot of math. You can trim that down by checking to see if

((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 > maxdist^2

Removes the sqrt until the end.

Answer 4

I would sell some of the spheres and buy a networked gps device for the remainder.