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

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

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

Два измерения

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

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

Смотрите также

Ссылки

  1. ^ Г. Т. Туссен, «Вычисление наибольших пустых кругов с ограничениями по местоположению», Международный журнал компьютерных и информационных наук , т. 12, № 5, октябрь 1983 г., стр. 347-358.
  2. ^ Меган Шустер, «Проблема самого большого пустого круга»
Получено с "https://en.wikipedia.org/w/index.php?title=Самая_большая_пустая_сфера&oldid=1150590725"