Задача об охране картинной галереи в случае ортогонального многоугольника на целочисленной решетке
УДК 519.67 ББК 22.1я431
Ключевые слова:
геометрия, ортогональный многоугольник
Аннотация
На сегодняшний день задача об охране картинной галереи является одной из хорошо изученных задач в области вычислительной геометрии. В реальном мире она возникает как задача об охране художественной галереи минимальным количеством средств наблюдения, которые наблюдают за всей галереей. В вычислительной геометрии план галереи представлен в виде простого многоугольника, а средство наблюдения – точкой внутри него.
Литература
1. Берг М., Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения. – М.: ДМК Пресс, 2017. – С 438.
2. O'Rourke, Joseph. Art Gallery Theorems and Algorithms // Oxford University Press. – 1987.
3. V. Chvatal. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. – 1975. – Т. 18. – С. 39–41.
4. S. Fisk. A short proof of Chvatal's watchman theorem // Journal of Combinatorial Theory, Series B. – 1978. – Т. 24, вып. 3. – С. 374.
5. Satyan L. Devadoss, Joseph O Rourke. Discrete and Computational Geometry. – Princeton University Press, 2011. – р. 255.
2. O'Rourke, Joseph. Art Gallery Theorems and Algorithms // Oxford University Press. – 1987.
3. V. Chvatal. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. – 1975. – Т. 18. – С. 39–41.
4. S. Fisk. A short proof of Chvatal's watchman theorem // Journal of Combinatorial Theory, Series B. – 1978. – Т. 24, вып. 3. – С. 374.
5. Satyan L. Devadoss, Joseph O Rourke. Discrete and Computational Geometry. – Princeton University Press, 2011. – р. 255.
Опубликован
2020-08-18
Раздел
Секция ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
