Top Qs
Timeline
Chat
Perspective

Largest empty sphere

From Wikipedia, the free encyclopedia

Largest empty sphere
Remove ads

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.

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).
Remove ads

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 .[1][2]

Remove ads

See also

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads