Bounding sphere
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, enclosing sphere or enclosing ball for that set is an n-dimensional solid sphere containing all of these objects.
In the plane the terms bounding or enclosing circle are used.
Used in computer graphics
and computational geometry
, a bounding sphere is a special type of bounding volume
. There are several fast and simple bounding sphere construction algorithms with a high practical value in real-time computer graphics applications.
In statistics
and operations research
, the objects are typically points, and generally the sphere of interest is the minimal bounding sphere, that is, the sphere with minimal radius among all bounding spheres. It may be proven that such sphere is unique: If there are two of them, then the objects in question lies within their intersection. But an intersection of two non-coinciding spheres of equal radius is contained in a sphere of smaller radius.
The problem of computing the center of a minimal bounding sphere is also known as the "unweighted Euclidean 1-center problem
".
, where groups of similar data points are classified together.
In 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 of 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, given a non-empty set of objects of finite extension in n-dimensional space
Space
Space is the boundless, three-dimensional extent in which objects and events occur and have relative position and direction. Physical space is often conceived in three linear dimensions, although modern physicists usually consider it, with time, to be part of a boundless four-dimensional continuum...
, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an n-dimensional solid sphere containing all of these objects.
In the plane the terms bounding or enclosing circle are used.
Used in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
and computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, a bounding sphere is a special type of bounding volume
Bounding volume
In computer graphics and computational geometry, a bounding volume for a set of objects is a closed volume that completely contains the union of the objects in the set. Bounding volumes are used to improve the efficiency of geometrical operations by using simple volumes to contain more complex...
. There are several fast and simple bounding sphere construction algorithms with a high practical value in real-time computer graphics applications.
In statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
and operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
, the objects are typically points, and generally the sphere of interest is the minimal bounding sphere, that is, the sphere with minimal radius among all bounding spheres. It may be proven that such sphere is unique: If there are two of them, then the objects in question lies within their intersection. But an intersection of two non-coinciding spheres of equal radius is contained in a sphere of smaller radius.
The problem of computing the center of a minimal bounding sphere is also known as the "unweighted Euclidean 1-center problem
1-center problem
The 1-center problem or minimax or minmax location problem is a classical combinatorial optimization problem in operations research of facilities location type...
".
Clustering
Such spheres are useful in clusteringClustering
Clustering can refer to the following:In demographics:* Clustering , the gathering of various populations based on factors such as ethnicity, economics or religion.In graph theory:...
, where groups of similar data points are classified together.
In 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
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
the clustering of values to an ideal point may also be used to reduce the number of inputs in order to obtain approximate values for NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
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
Least squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
point is computed to represent the cluster.
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 GPLGNU General Public LicenseThe GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
license) - Minimal bounding sphere of a set of balls in dimensions up to 30 in CGALCGALThe Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
, the Computational Geometry Algorithms Library
External links
- Smallest Enclosing Circle Problem – describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm