Largest empty sphere

File:Espace octaedrique cubique faces centrees.svg

The dashed circle is the outline of the largest empty sphere in the close-packing of spheres. See also Interstitial defect.

File:Plus grand cercle vide voronoi.svg

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 $\mathrm{\Theta }(n\log n)$.

See also

• Bounding sphere
• Farthest-first traversal
• Largest empty rectangle