[[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. See also ''Interstitial defect''.]]
thumb|Finding the largest empty circle using the Voronoi diagram (two solutions).
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 <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 *Farthest-first traversal *Largest empty rectangle
==References==
{{reflist}}
Category:Geometric algorithms