Editing Bounding sphere

{{Short description|Sphere that contains a set of objects}}
{{for|the planar problem|Bounding circle}}
[[Image:Smallest circle problem.svg|thumb|right|300px|Some instances of the [[smallest bounding circle]], the case of the bounding sphere in 2 dimensions.]]

In [[mathematics]], given a non-empty set of objects of finite extension in <math>d</math>-dimensional [[space]], for example a set of points, a '''bounding sphere''', '''enclosing sphere''' or '''enclosing ball''' for that set is a <math>d</math>-dimensional [[solid sphere]] containing all of these objects.

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.{{r|epos}}

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 a sphere is unique: If there are two of them, then the objects in question lie 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]]".

==Applications==

===Clustering===
Such spheres are useful in [[Cluster analysis|clustering]], where groups of similar data points are classified together.

In [[statistical analysis]] the [[scattering (statistics)|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.

==Algorithms==
There are exact and approximate algorithms for solving the bounding sphere problem.

===Linear programming===
[[Nimrod Megiddo]] studied the 1-center problem extensively and published on it at least five times in the 1980s.<ref>{{cite web |url=http://theory.stanford.edu/~megiddo/bio.html |title = Nimrod Megiddo's resume and publications}}</ref> 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.  When the dimension <math>d</math> is taken into account, the execution time complexity is <math>O(2^{O(d^2)} n)</math>,{{r|meg88}}{{r|chan18}} which is impractical for high-dimensional applications.

In 1991, [[Emo Welzl]] proposed a much simpler [[randomized algorithm]], generalizing a randomized [[linear programming]] algorithm by [[Raimund Seidel]].  The expected running time of Welzl's algorithm is <math>O((d+1)(d+1)!n)</math>, which again reduces to <math>O(n)</math> for any fixed dimension <math>d</math>.  The paper provides experimental results demonstrating its practicality in higher dimensions.{{r|welzl92}}  A more recent deterministic algorithm of [[Timothy Chan]] also runs in <math>O(n)</math> time, with a smaller (but still exponential) dependence on the dimension.{{r|chan18}}

The open-source [[Computational Geometry Algorithms Library]] (CGAL) contains an implementation of Welzl's algorithm.<ref>[http://doc.cgal.org/latest/Bounding_volumes/classCGAL_1_1Min__sphere__of__spheres__d.html CGAL 4.3 - Bounding Volumes - Min_sphere_of_spheres_d], retrieved 2014-03-30.</ref>

===Ritter's bounding sphere===
In 1990, Jack Ritter proposed a simple algorithm to find a non-minimal bounding sphere.{{r|Ritter1990}} It is widely used in various applications for its simplicity. The algorithm works in this way:

#Pick a point <math>x</math> from <math>P</math>, search a point <math>y</math> in <math>P</math>, which has the largest distance from <math>x</math>;
#Search a point <math>z</math> in <math>P</math>, which has the largest distance from <math>y</math>. Set up an initial ball <math>B</math>, with its centre as the midpoint of <math>y</math> and <math>z</math>, the radius as half of the distance between <math>y</math> and <math>z</math>;
#If all points in <math>P</math> are within ball <math>B</math>, then we get a bounding sphere. Otherwise, let <math>p</math> be a point outside the ball, constructs a new ball covering both point <math>p</math> and previous ball. Repeat this step until all points are covered.

Ritter's algorithm runs in time <math>O(nd)</math> on inputs consisting of <math>n</math> points in <math>d</math>-dimensional space, which makes it very efficient. However, it gives only a coarse result which is usually 5% to 20% larger than the optimum.{{r|Ritter1990}}

===Core-set based approximation===
Bădoiu et al. presented a <math>1+\varepsilon</math> approximation to the bounding sphere problem,{{r|Badoiu2002}} where a <math>1+\varepsilon</math> approximation means that the constructed sphere has radius at most <math>(1+\varepsilon)r</math>, where <math>r</math> is the smallest possible radius of a bounding sphere.

A [[coreset]] is a small subset, that a <math>1+\varepsilon</math> 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{{r|kumar2003}} so that it runs in time <math>O(\frac{nd}{\epsilon}+ \frac{1}{\epsilon^{4.5}}\log{\frac{1}{\epsilon}})</math>.

===Fischer's exact solver===
Fischer et al. (2003) proposed an exact solver, though the algorithm does not have a polynomial running time in the worst case.{{r|Fischer2003}} 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.{{r|Fischer2003}} A C++ implementation of the algorithm is available as an open-source project.<ref>[https://github.com/hbf/miniball miniball open-source project]</ref>

=== Extremal points optimal sphere ===
{{harvtxt|Larsson|2008}} proposed the "extremal points optimal sphere" method with controllable speed to accuracy approximation to solve the bounding sphere problem. This method works by taking a set of <math>s</math> direction vectors and projecting all points onto each vector in <math>s</math>; <math>s</math> serves as a speed-accuracy trade-off variable. An exact solver is applied to the <math>2s</math> extremal points of these projections. The algorithm then iterates over the remaining points, if any, growing the sphere if necessary. For large <math>n</math> this method is orders of magnitude faster than exact methods, while giving comparable results. It has a worst case time of <math>O(sn)</math>. {{r|epos}}

== See also ==
*[[Bounding volume]]
*[[Circumscribed sphere]], [[circumscribed circle]]

== References  ==
{{reflist|refs=

<ref name=Badoiu2002>{{citation
 | last1 = Bādoiu | first1 = Mihai
 | last2 = Har-Peled | first2 = Sariel | author2-link = Sariel Har-Peled
 | last3 = Indyk | first3 = Piotr | author3-link = Piotr Indyk
 | contribution = Approximate clustering via core-sets
 | contribution-url = https://www.cs.duke.edu/courses/spring07/cps296.2/papers/badoiu02approximate.pdf
 | doi = 10.1145/509907.509947
 | mr = 2121149
 | pages = 250–257
 | publisher = ACM | location = New York, NY, US
 | title = Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing
 | year = 2002| s2cid = 5409535
 | citeseerx = 10.1.1.4.9395
 }}</ref>

<ref name=epos>{{citation
 | last = Larsson | first = Thomas
 | contribution = Fast and tight fitting bounding spheres
 | contribution-url = https://www.ep.liu.se/ecp/article.asp?issue=034&article=9
 | series = Linköping Electronic Conference Proceedings
 | publisher = Linköping University | location = Linköping, Sweden
 | title = SIGRAD 2008: The Annual SIGRAD Conference, Special Theme: Interaction, November 27-28, 2008, Stockholm, Sweden
 | volume = 34
 | year = 2008}}</ref>

<ref name=Fischer2003>{{citation
 | last1 = Fischer | first1 = Kaspar
 | last2 = Gärtner | first2 = Bernd
 | last3 = Kutz | first3 = Martin
 | editor1-last = Battista | editor1-first = Giuseppe Di
 | editor2-last = Zwick | editor2-first = Uri
 | contribution = Fast smallest-enclosing-ball computation in high dimensions
 | contribution-url = https://people.inf.ethz.ch/gaertner/subdir/texts/own_work/seb.pdf
 | doi = 10.1007/978-3-540-39658-1_57
 | pages = 630–641
 | publisher = Springer, Berlin
 | series = Lecture Notes in Computer Science
 | title = Algorithms: ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings
 | volume = 2832
 | isbn = 978-3-540-20064-2
 | year = 2003| url = http://www.mpi-inf.mpg.de/~mkutz/pubs/FiGaeKu_SmallEnclBalls.pdf
 }}</ref>

<ref name=kumar2003>{{citation
 | last1 = Kumar | first1 = Piyush
 | last2 = Mitchell | first2 = Joseph S. B. | author2-link = Joseph S. B. Mitchell
 | last3 = Yıldırım | first3 = E. Alper
 | editor-last = Ladner | editor-first = Richard E.
 | contribution = Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions
 | pages = 45–55
 | publisher = SIAM | location = Philadelphia, PA, US
 | title = Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments, Baltimore, MD, USA, January 11, 2003
 | year = 2003}}</ref>

<ref name=Ritter1990>{{citation
 | last = Ritter | first = Jack
 | editor-last = Glassner | editor-first = Andrew S.
 | contribution = An efficient bounding sphere
 | isbn = 0-12-286166-3
 | location = San Diego, CA, US
 | pages = 301–303
 | publisher = Academic Press Professional, Inc.
 | title = Graphics Gems
 | year = 1990}}</ref>

<ref name=meg88>{{cite journal
 | last = Megiddo | first = Nimrod | author-link = Nimrod Megiddo
 | title = Linear programming in linear time when the dimension is fixed
 | doi = 10.1145/2422.322418
 | journal = Journal of the ACM
 | pages = 114–147
 | volume = 33
 | issue = 1
 | year = 1988 | s2cid = 12686747 | doi-access = free
 }}</ref>

<ref name=welzl92>{{citation
 | last = Welzl | first = Emo | author-link = Emo Welzl
 | editor-last = Maurer | editor-first = Hermann
 | contribution = Smallest enclosing disks (balls and ellipsoids)
 | doi = 10.1007/BFb0038202
 | mr = 1254721
 | pages = 359–370
 | publisher = Springer | location = Berlin, Germany
 | series = Lecture Notes in Computer Science
 | title = New Results and New Trends in Computer Science: Graz, Austria, June 20–21, 1991, Proceedings
 | url = https://scholar.archive.org/work/7rcfutcwczbrnkmey7f42vscom
 | volume = 555
 | isbn = 3-540-54869-6 | year = 1991 }}</ref>

<ref name=chan18>{{cite journal
 | last = Chan | first = Timothy | author-link = Timothy Chan
 | title = Improved deterministic algorithms for linear programming in low dimensions
 | doi = 10.1145/3155312
 | journal = ACM Transactions on Algorithms
 | volume = 14
 | issue = 3
 | pages = Article 30, 10 pages
 | year = 2018 | s2cid = 9345339 }}</ref>

}}

== External links ==
* [http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm Smallest Enclosing Circle Problem] – describes several algorithms for enclosing a point set, including Megiddo's linear-time algorithm

[[Category:Geometric algorithms]]
[[Category:Spheres]]