Bounding sphere
In mathematics, given a non-empty set of objects of finite extension in
There are several fast and simple bounding sphere construction algorithms with a high practical value in real-time computer graphics applications.
It may be proven that such a sphere is unique: If there are two of them, then the objects in question lie within their intersection.
Such spheres are useful in clustering, 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 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.
There are exact and approximate algorithms for solving the bounding sphere problem.
Nimrod Megiddo studied the 1-center problem extensively and published on it at least five times in the 1980s.
[2] In 1983, he proposed a "prune and search" algorithm which finds the optimum bounding sphere and runs in linear time if the dimension is fixed as a constant.
In 1991, Emo Welzl proposed a much simpler randomized algorithm, generalizing a randomized linear programming algorithm by Raimund Seidel.
The paper provides experimental results demonstrating its practicality in higher dimensions.
[5] A more recent deterministic algorithm of Timothy Chan also runs in
[6] In 1990, Jack Ritter proposed a simple algorithm to find a non-minimal bounding sphere.
However, it gives only a coarse result which is usually 5% to 20% larger than the optimum.
expansion of the solution on the subset is a bounding sphere of the whole set.
The coreset is constructed incrementally by adding the farthest point into the set in each iteration.
Kumar et al. improved this approximation algorithm[9] so that it runs in time
Fischer et al. (2003) proposed an exact solver, though the algorithm does not have a polynomial running time in the worst case.
[10] The algorithm is purely combinatorial and implements a pivoting scheme similar to the simplex method for linear programming, used earlier in some heuristics.
It starts with a large sphere that covers all points and gradually shrinks it until it cannot be shrunk further.
The algorithm features correct termination rules in cases of degeneracies, overlooked by prior authors; and efficient handling of partial solutions, which produces a major speed-up.
The authors verified that the algorithm is efficient in practice in low and moderately low (up to 10,000) dimensions and claim it does not exhibit numerical stability problems in its floating-point operations.
[11] Larsson (2008) proposed the "extremal points optimal sphere" method with controllable speed to accuracy approximation to solve the bounding sphere problem.
The algorithm then iterates over the remaining points, if any, growing the sphere if necessary.
