Bounding Spheres

Bounding spheres are a real issue in modern math. They are widely used for clustering of data, however, no efficient algorithm exists to build them. Let’s apply a naive technique to the problem.

Preparations

Let’s start by some notations. Let n be the number of points, d the dimension (we want an algorithm that works with n dimensional hyperspheres), and we will use big O notation for asymptotic complexity in operations. For instance, an O(n) algorithm is an algorithm that doubles the execution time if we double the number of points.

Then, we have to read n points, each containing d values. It means that we can’t have a better complexity than O(n*d). It is our mathematics limit, and does not depend on the algorithm.

The drawings are in 2D for simplicity, a bounding circle has at most 3 points on its boundary, try to find them on the figure!

Method

Our approach is quite exotic: normally finding a bounding sphere consists of finding the center of the sphere, then its radius, because we can trivially find the radius from the center in O(nd) (which means no more supplementary complexity). Here we will do both things at the same time: find an approximate radius, that gives us a center, and then we can recompute the radius if necessary.

The algorithm loop is as such:

• … the points in
• Compute spheres

An almost-bounding sphere of 800 points

Quality Evaluation

The first thing is: the algorithm ends. That is always a good point. We will compare it on precision for the center, and operations complexity.

Precision

Due to the method used, the bounding sphere is not centered. Its difference from the actual center seems to be a measurement of the skewness of the data.

Operations complexity/Time complexity

We assume that operations complexity is roughly equal to time complexity. Here is a graph of the measured time complexity.

A graph of the execution time over number of points. Blue line is a straight line.

The dots indicate the execution time depending on the number of points, which means a bounding sphere of 10,000 points takes about 5 seconds. The interesting part is that the blue line is a reference straight line for an O(n) points complexity. Both lines do correspond, which means we achieved linear complexity!

Conclusion

We developed a fast minimal bounding sphere algorithm. It is not perfect because the center can be badly placed, but the results are good enough for an actual use. The main limit is that it performs badly when the skewness of the data is high.