Largest empty sphere
Appearance
![](http://upload.luquay.com/wikipedia/commons/thumb/8/8b/Espace_octaedrique_cubique_faces_centrees.svg/220px-Espace_octaedrique_cubique_faces_centrees.svg.png)
![](http://upload.luquay.com/wikipedia/commons/thumb/9/96/Plus_grand_cercle_vide_voronoi.svg/220px-Plus_grand_cercle_vide_voronoi.svg.png)
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[edit]
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 .[1][2]
See also[edit]
References[edit]
- ^ 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, "The Largest Empty Circle Problem"