Editing Bounding sphere (section)

===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>