Наибольшая пустая сфера
Задача о наибольшей пустой сфере — это задача нахождения гиперсферы наибольшего радиуса в d-мерном пространстве, внутренность которой не перекрывает какое-либо из заданных препятствий.
Пунктирная окружность очерчивает наибольшую пустую сферу в задаче плотной упаковки равных сфер. См. также Межузельный атом.
Нахождение наибольшей пустой окружности с помощью диаграммы Вороного (два решения).
Двумерное пространство
Задача о наибольшей пустой окружности — это задача нахождения окружности наибольшего радиуса на плоскости, внутренность которой не перекрывает какое-либо из заданных препятствий.
Общий частный случай следующий. Пусть задано n точек на плоскости, найти наибольшую окружность, находящуюся в выпуклой оболочкеll этих точек и не включающую ни одной из этих точек. Задачу можно решить с помощью диаграмм Вороного за оптимальное время [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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.