Largest empty sphere
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.
The dashed circle is the outline of the largest empty sphere in the close-packing of spheres. See also Interstitial defect.
Finding the largest empty circle using the Voronoi diagram (two solutions).
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]
gollark: "Light" how?
gollark: As the privacy policy says in clause 5.1, "If any aspect is not utterly harmonious, gratefully bring it to our notice and we shall strive to earn your satisfaction.".
gollark: <@490656381662396418> What specifically do you want from "PotatOS Light"?
gollark: Anyway, PotatOS Hypercycle is going to maybe be vaguely lighter in some ways.
gollark: You really can't do the "mysterious/obfuscation" thing.
References
- 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"
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.