Меню Главная Случайная статья Настройки Наибольшая пустая сфера Материал из https://ru.wikipedia.org Задача о наибольшей пустой сфере — это задача нахождения гиперсферы наибольшего радиуса в d-мерном пространстве, внутренность которой не перекрывает какое-либо из заданных препятствий. Содержание 1 Двумерное пространство 2 См. также 3 Примечания 4 Литература Двумерное пространство Задача о наибольшей пустой окружности — это задача нахождения окружности наибольшего радиуса на плоскости, внутренность которой не перекрывает какое-либо из заданных препятствий. Общий частный случай: пусть задано n точек на плоскости, найти наибольшую окружность, находящуюся в выпуклой оболочкеll этих точек и не включающую ни одной из этих точек. Задачу можно решить с помощью диаграмм Вороного за оптимальное время ${\displaystyle \Theta (n\,\log \,n)}$[1][2]. См. также Ограничивающая сфера Переход к наиболее удалённым[англ.] Задача о наибольшем пустом прямоугольнике Примечания Toussaint, 1983, с. 347-358. Schuster. Литература Toussaint G. T. Computing largest empty circles with location constraints // International Journal of Computer and Information Sciences. — 1983. — Октябрь (т. 12, вып. 5). Megan Schuster. The Largest Empty Circle Problem.