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