Largest empty sphere

File:Espace octaedrique cubique faces centrees.svg. See also Interstitial defect.]]

File:Plus grand cercle vide voronoi.svg

In computational geometry, the largest empty sphere problem is the problem of finding a 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 of largest radius in the plane 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 and enclosing none of them. The problem may be solved using Voronoi diagrams in optimal time $\backslash Theta(n\backslash ,\; \backslash log\backslash ,\; n)$.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.Megan Schuster, [https://www.cs.swarthmore.edu/~adanner/cs97/s08/papers/schuster.pdf "The Largest Empty Circle Problem"]