Największa pusta kula

Przerywane koło to zarys największej pustej kuli w ścisłym upakowaniu kul . Zobacz także Defekt śródmiąższowy .

Znalezienie największego pustego koła za pomocą diagramu Woronoja (dwa rozwiązania).

W geometrii obliczeniowej największym problemem pustej kuli jest problem znalezienia hipersfery o największym promieniu w przestrzeni d -wymiarowej, której wnętrze nie pokrywa się z żadnymi zadanymi przeszkodami.

Dwa wymiary

największego pustego koła to problem znalezienia koła o największym promieniu na płaszczyźnie , którego wnętrze nie pokrywa się z żadną zadaną przeszkodą.

Typowy przypadek szczególny jest następujący. Biorąc pod uwagę n punktów na płaszczyźnie, znajdź największy okrąg wyśrodkowany w ich wypukłym kadłubie i nie obejmujący żadnego z nich. Problem można rozwiązać za pomocą diagramów Woronoja w optymalnym czasie ${\ Displaystyle \ Theta (n \, \ log \, n)}$ .

Zobacz też