Граф видимости

Графы видимости применяются для поиска кратчайших евклидовых путей между полигональными препятствиями на плоскости: кратчайший путь между двумя препятствиями состоит из прямолинейных сегментов, за исключением случаев поворота на вершинах препятствий. Следовательно, кратчайший евклидов путь соответствует кратчайшему пути в графе видимости, построенном по начальной и конечной точке и вершинам препятствий. Поэтому задача поиска кратчайшего евклидова пути разбивается на две стадии: построение графа видимости и применение алгоритма поиска кратчайшего пути, например алгоритма Дейкстры. Для планирования движения робота, размеры которого сравнимы с размерами препятствий, используется аналогичный подход, предварительно «увеличив» препятствия на размер робота^[2]. Метод графа видимости для поиска кратчайших евклидовых путей был впервые исследован Нильсом Нильссоном (англ. Nils Nilsson) в 1969 году при разработке планирования движения для Shakey, а также описан в 1973 году российскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.

Графы видимости используются также для расчёта расположения радиоантенн, а также в архитектуре и градостроительстве в рамках анализа графов видимости.

Граф видимости множества точек на одной прямой может быть рассмотрен как графическое представление временного ряда. Такой подход связывает временные ряды, динамические системы и теорию графов.

Граф видимости простого многоугольника строится по его вершинам, а в качестве препятствия выступает внешняя область многоугольника. Графы видимости простых многоугольников всегда гамильтоновы, поскольку граница многоугольника образует гамильтонов цикл в графе видимости. При этом не любой граф видимости задаёт некоторый простой многоугольник. В то же время эффективной алгоритмической характеристики графов видимости простых многоугольников на сегодняшний день не существует. Такие графы не обязательно принадлежат к известным структурированным семействам: они могут не относиться к перфектным графам, круговым графам или кордальным графам^[3]. Исключением является то, что графы видимости простых многоугольников всегда cop-win-графы^[4].

Задача о галерее состоит в нахождении минимального множества точек (охранников), из которых видна вся область с учётом препятствий. Некоторые формулировки этой задачи могут быть сведены к поиску доминирующего множества в графе видимости.

Битангента системы многоугольников или кривых — это прямая, касающаяся одновременно двух многоугольников (или кривой в двух точках) и не пересекающая другие. Битангенты среди вершин задают подмножество графа видимости, в котором вершины многоугольника служат узлами, а сами многоугольники — препятствиями. Построение графа видимости на основе битангент ускоряет поиск кратчайших евклидовых путей, так как кратчайший путь в плоскости может входить и выходить из границы препятствия только вдоль битангенты.