Самая большая пустая сфера

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

Два измерения [ править ]

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

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

См. также [ править ]

Ссылки [ править ]

^ GT Туссен, «Вычисление крупнейших пустых кругов с ограничениями по местоположению», Международный журнал компьютерных и информационных наук , том. 12, № 5, октябрь 1983 г., стр. 347-358.
^ Меган Шустер, «Самая большая проблема с пустым кругом»

[1] GT Туссен, «Вычисление крупнейших пустых кругов с ограничениями по местоположению», Международный журнал компьютерных и информационных наук , том. 12, № 5, октябрь 1983 г., стр. 347-358.

[2] Меган Шустер, «Самая большая проблема с пустым кругом»

[1]

[2]