Largest empty sphere explained

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.

\Theta(n log n) .^{[1] [2]}

See also

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

Notes and References

1. 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.
2. Megan Schuster, "The Largest Empty Circle Problem"