Största tomma sfären

Den streckade cirkeln är konturen av den största tomma sfären i tätpackningen av sfärer . Se även Interstitiell defekt .

Hitta den största tomma cirkeln med Voronoi-diagrammet (två lösningar).

Inom beräkningsgeometri är det största problemet med tomma sfärer problemet med att hitta en hypersfär med största radie i d -dimensionell rymd vars inre inte överlappar med några givna hinder.

Två dimensioner

Det största problemet med tom cirkel är problemet med att hitta en cirkel med största radie i planet vars inre inte överlappar med några givna hinder.

Ett vanligt specialfall är följande. Med tanke på n punkter i planet, hitta en största cirkel centrerad inom deras konvexa skrov och omsluter ingen av dem. Problemet kan lösas med Voronoi-diagram i optimal tid $\Theta (n\,\log \,n)$ .

Se även

• Avgränsande sfär
• Längst-första traversering
• Största tomma rektangeln