WikiSort.ru - Не сортированное

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

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

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

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

См. также

• Ограничивающая сфера
• Переход к наиболее удалённым^[en]
• Наибольший пустой прямоугольник^[en]

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.