# Largest empty sphere

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Largest_empty_sphere
> Markdown URL: https://mediated.wiki/source/Largest_empty_sphere.md
> Source: https://en.wikipedia.org/wiki/Largest_empty_sphere
> Source revision: 1150590725
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

[[File:Espace octaedrique cubique faces centrees.svg|thumb|The dashed circle is the outline of the largest empty sphere in the [close-packing of spheres](/source/Close-packing_of_equal_spheres). See also ''[Interstitial defect](/source/Interstitial_defect)''.]]

thumb|Finding the largest empty circle using the Voronoi diagram (two solutions).

In [computational geometry](/source/computational_geometry), the '''largest empty sphere''' problem is the problem of finding a [hypersphere](/source/hypersphere) of largest radius  in ''d''-dimensional space whose interior does not overlap with any given obstacles.

==Two dimensions== 
The '''largest empty circle''' problem is the problem of finding a [circle](/source/circle) of largest radius in [the plane](/source/Plane_(geometry)) whose interior does not overlap with any given obstacles.

A common special case is as follows. Given ''n'' points in the plane, find a largest circle centered within their [convex hull](/source/convex_hull) and enclosing none of them. The problem may be solved using [Voronoi diagram](/source/Voronoi_diagram)s in  [optimal time](/source/time_complexity) <math>\Theta(n\, \log\, n)</math>.<ref>G. T. Toussaint, "Computing largest empty circles with location constraints," ''International Journal of Computer and Information Sciences'', vol. 12, No. 5, October, 1983, pp. 347-358.</ref><ref>Megan Schuster, [https://www.cs.swarthmore.edu/~adanner/cs97/s08/papers/schuster.pdf "The Largest Empty Circle Problem"]</ref>

==See also==
*[Bounding sphere](/source/Bounding_sphere)
*[Farthest-first traversal](/source/Farthest-first_traversal)
*[Largest empty rectangle](/source/Largest_empty_rectangle)

==References==

{{reflist}}

Category:Geometric algorithms

---
Adapted from the Wikipedia article [Largest empty sphere](https://en.wikipedia.org/wiki/Largest_empty_sphere) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Largest_empty_sphere?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.