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

Largest empty sphere
Пунктирный круг - это контур самой большой пустой сферы в плотная упаковка сфер. Смотрите также Межстраничный дефект.
Нахождение наибольшего пустого круга с помощью диаграммы Вороного (два решения).

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

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

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

Общий частный случай выглядит следующим образом. Данный п точки на плоскости, найдите самый большой круг с центром в их выпуклая оболочка и не охватывая ни одного из них. Проблема может быть решена с помощью Диаграммы Вороного в оптимальное время .[1][2]

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

использованная литература

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