В вычислительной геометрии и планировании движения робота [1] граф видимости — это граф взаимовидимых местоположений, обычно для набора точек и препятствий на евклидовой плоскости . Каждый узел в графе представляет местоположение точки, а каждое ребро представляет видимое соединение между ними. То есть, если отрезок прямой, соединяющий два местоположения, не проходит через какое-либо препятствие, между ними в графе рисуется ребро. Когда набор местоположений лежит на линии, это можно понимать как упорядоченную серию. Поэтому графы видимости были расширены до области анализа временных рядов .
Графы видимости могут использоваться для поиска евклидовых кратчайших путей среди набора многоугольных препятствий на плоскости: кратчайший путь между двумя препятствиями следует по прямолинейным отрезкам, за исключением вершин препятствий , где он может поворачивать, поэтому евклидовый кратчайший путь является кратчайшим путем в графе видимости, который имеет в качестве узлов начальную и конечную точки и вершины препятствий. [2] Таким образом, задача евклидового кратчайшего пути может быть разложена на две более простые подзадачи: построение графа видимости и применение к графу алгоритма кратчайшего пути, такого как алгоритм Дейкстры . Для планирования движения робота, имеющего немалый размер по сравнению с препятствиями, можно использовать аналогичный подход после расширения препятствий для компенсации размера робота. [2] Лозано-Перес и Уэсли (1979) связывают метод графа видимости для кратчайших евклидовых путей с исследованиями 1969 года Нильса Нильссона по планированию движения для робота Шейки , а также цитируют описание этого метода 1973 года, сделанное русскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.
Графики видимости также могут использоваться для расчета размещения радиоантенн или в качестве инструмента, используемого в архитектуре и городском планировании посредством анализа графика видимости .
Граф видимости набора местоположений, лежащих на одной линии, можно интерпретировать как теоретико-графическое представление временного ряда. [3] Этот частный случай устанавливает мост между временными рядами , динамическими системами и теорией графов .
Граф видимости простого многоугольника имеет вершины многоугольника в качестве точек расположения, а внешнюю часть многоугольника в качестве единственного препятствия. Графы видимости простых многоугольников должны быть гамильтоновыми графами : граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости порождают простой многоугольник. Однако эффективная алгоритмическая характеристика графов видимости простых многоугольников остается неизвестной. Эти графы не попадают во многие известные семейства хорошо структурированных графов: они могут не быть идеальными графами , круговыми графами или хордовыми графами . [4] Исключением из этого явления является то, что графы видимости простых многоугольников являются графами cop-win . [5]
Задача о художественной галерее — это задача нахождения небольшого набора точек, из которого видны все остальные точки, не являющиеся препятствиями. Некоторые формы задачи о художественной галерее можно интерпретировать как нахождение доминирующего набора в графе видимости.
Касательные к двум точкам системы многоугольников или кривых — это линии, которые касаются двух из них, не проникая в них в точках контакта. Касательные к двум точкам набора многоугольников образуют подмножество графа видимости, в котором вершины многоугольника являются узлами, а сами многоугольники — препятствиями. Подход графа видимости к задаче поиска кратчайшего евклидового пути можно ускорить, сформировав граф из касательных к двум точкам вместо использования всех ребер видимости, поскольку кратчайший евклидов путь может входить или выходить из границы препятствия только вдоль касательной к двум точкам. [6]