Оглавление
Самая большая пустая сфера
-
Основная задача вычислительной геометрии
- Нахождение гиперсферы наибольшего радиуса, внутренняя часть которой не пересекается с препятствиями.
-
Задача о самом большом пустом круге
- Нахождение круга наибольшего радиуса на плоскости, не пересекающегося с препятствиями.
- Частный случай задачи о наибольшем пустом круге – нахождение наибольшей окружности внутри выпуклой оболочки n точек на плоскости.
-
Решение задачи о самом большом пустом круге
- Использование диаграмм Вороного для решения задачи с временной сложностью Θ(n log n).
-
Связанные задачи
- Упоминание других задач вычислительной геометрии, таких как нахождение ограничивающей сферы, самого дальнего прямоугольника и рекомендации по их решению.