Архив статей журнала
Статья посвящена исследованию задачи об охране картинной галереи на поверхности выпуклого многогранника. Приводится основная теорема о картинной галерее, а также описание алгоритма поиска максимального паросочетания в двойственном графе выпуклого многогранника.
Статья посвящена классификации функционалов Минковского в трехмерном цифровом пространстве на основе типов окрестности двумерного цифрового пространства. В работе выдвигается алгоритм нахождения функционалов Минковского трехмерного цифрового пространства, основанного на двумерном случае.
Статья посвящена исследованию задачи об охране картинной галереи, когда план ее интерьера представлен в виде ортогонального многоугольника. Проводится обзор известных результатов, и получен псевдокод алгоритма расстановки охранников
Статья посвящена исследованию функционалов Минковского в двумерном цифровом пространстве. В работе изучается алгоритм нахождения функционалов Минковского.
В данной работе описано обобщение алгоритма Форчуна для построения диаграммы Вороного множества точек на сфере. Проведена оценка эффективности данного алгоритма.
На сегодняшний день задача об охране картинной галереи является одной из хорошо изученных задач в области вычислительной геометрии. В реальном мире она возникает как задача об охране художественной галереи минимальным количеством средств наблюдения, которые наблюдают за всей галереей. В вычислительной геометрии план галереи представлен в виде простого многоугольника, а средство наблюдения - точкой внутри него.