Bounding sphere
From Wikipedia, the free encyclopedia
In mathematics, given a non-empty set of objects of finite extension in n-dimensional space, for example a set of points, a bounding sphere for that set is an n-dimensional solid sphere containing each of these objects.
Used in computer graphics and computational geometry, a bounding sphere is a special type of bounding volume.
In statistics and operations research, the objects are typically points, and generally the sphere of interest is the minimal bounding sphere, that is, the unique sphere with minimal radius among all bounding spheres. Such spheres are useful in clustering, where groups of similar data points are classified together. In the statistical analysis the scattering of data points within a sphere may be attributed to measurement error or natural (usually thermal) processes, in which case the cluster represents a perturbation of an ideal point. In some circumstances this ideal point may be used as a substitute for the points in the cluster, advantageous in reducing calculation time. In operations research the clustering of values to an ideal point may also be used to reduce the number if inputs in order to obtain approximate values for NP-hard problems in a reasonable time. The point chosen is not usually the center of the sphere, as this can be biased by outliers, but instead some form of average location such as a least squares point is computed to represent the cluster.
[edit] Software for computing the minimal bounding sphere
- Miniball software — C++ software to compute the minimal bounding sphere of a pointset in dimensions up to 30 (distributed under the GPL license)
- Computational Geometry Algorithms Library CGAL — a C++ library with a package, Min_sphere_of_spheres_d, to compute the minimal bounding sphere of a set of balls in dimensions up to 30 (distributed under the GPL license)
[edit] External links
- Smallest Enclosing Circle Problem – describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm
