Наибольшая пустая сфера

Пунктирная окружность очерчивает наибольшую пустую сферу в задаче плотной упаковки равных сфер. См. также Межузельный атом.

Нахождение наибольшей пустой окружности с помощью диаграммы Вороного (два решения).

Задача о наибольшей пустой сфере — это задача нахождения гиперсферы наибольшего радиуса в d-мерном пространстве, внутренность которой не перекрывает какое-либо из заданных препятствий.

Двумерное пространство

Задача о наибольшей пустой окружности — это задача нахождения окружности наибольшего радиуса на плоскости, внутренность которой не перекрывает какое-либо из заданных препятствий.

Общий частный случай следующий. Пусть задано n точек на плоскости, найти наибольшую окружность, находящуюся в выпуклой оболочкеll этих точек и не включающую ни одной из этих точек. Задачу можно решить с помощью диаграмм Вороного за оптимальное время $\mathrm{\Theta }(n\log n)$Шаблон:SfnШаблон:Sfn.

См. также

• Ограничивающая сфера
• Шаблон:Не переведено 5
• Задача о наибольшем пустом прямоугольнике

Литература

• Шаблон:Статья
• Шаблон:Статья