Största tomma sfären

Det största problemet med tomma sfärer är problemet med att hitta en hypersfär med den största radien i det d -dimensionella rummet, vars inre inte överlappar något av de givna hindren.

Tvådimensionellt utrymme

Problemet med den största tomma cirkeln är problemet med att hitta en cirkel med den största radien på ett plan vars inre inte överlappar något av de givna hindren.

Det allmänna specialfallet är följande. Låt n punkter på planet ges, hitta den största cirkeln som finns i det konvexa skrovet av dessa punkter och inte inkluderar någon av dessa punkter. Problemet kan lösas med Voronoi-diagram i optimal tid [1] [2] .

Se även

• avgränsande sfär
• Gå längst
• Problemet med den största tomma rektangeln

Anteckningar

1. ↑ Toussaint, 1983 , sid. 347-358.
2. ↑ Schuster .

Litteratur

• Toussaint GT Computing största tomma cirklar med platsbegränsningar // International Journal of Computer and Information Sciences. - 1983. - Oktober ( vol. 12 , nummer 5 ).
• Megan Schuster. Det största problemet med den tomma cirkeln .