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

Перейти к навигацииПерейти к поиску

В вычислительной геометрии и планировании движений[англ.] роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность. Графы видимости, таким образом, распространяются на область анализа временных рядов.

Приложения

Графы видимости можно использовать для поиска кратчайших путей[англ.] среди многоугольных препятствий на плоскости — кратчайший путь между двумя препятствиями проходит по прямой и поворачивает в вершинах препятствий, так что кратчайший путь является кратчайшим путём в графе видимости, вершинами которого являются начальная и конечная точки и вершины препятствий[1][2]. Таким образом, задача о кратчайшем пути может быть разбита на две более простые задачи — построение графа видимости и применение к графу алгоритма кратчайшего пути, такого как алгоритм Дейкстры. Для планирования движения робота, который имеет заметный размер по сравнению с препятствиями, может быть использован похожий подход путём увеличения препятствий для компенсации размера робота[1][2]. Лозано-Перец и Весли[2] приписывают метод графа видимости для кратчайшего пути на евклидовой плоскости исследованию 1969 года Нильса Нильссона по планированию движения робота Шеки и цитируют описание этого метода в 1973-м году русскими математиками М. Б. Игнатьевым, Ф. М. Кулаковым и А. М. Покровским.

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

Если множество точек пространства лежит на прямой, их можно понимать как упорядоченную последовательность[3]. Этот частный случай строит мост между временными рядами, динамическими системами и теорией графов.

Характеризация

Граф видимости простого многоугольника (т.е. без пересечения сторон) имеет вершины в качестве точек в пространстве и внешнюю область многоугольника в качестве препятствия. Графы видимости простых многоугольников должны быть гамильтоновыми — граница многоугольника образует гамильтонов цикл в графе видимости. Известно, что не все графы видимости образуют простой многоугольник. Фактически, графы видимости простых многоугольников не обладают характеристиками какого-то класса графов[4].

Связанные задачи

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

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

См. также

  • Нечёткий архитектурный пространственный анализ[англ.]
  • Пространственный синтаксис[англ.]

Примечания

  1. ↑ 1 2 de Berg, van Kreveld, Overmars, Schwarzkopf, 2000, с. sections 5.1, 5.3.
  2. ↑ 1 2 3 Lozano-Pérez, Wesley, 1979.
  3. ↑ Lacasa et al., From time series to complex networks: the visibility graph, PNAS 105, 13 (2008). Дата обращения: 8 декабря 2016. Архивировано 13 июня 2017 года.
  4. ↑ Ghosh, 1997, с. 143–162.
  5. ↑ de Berg, van Kreveld, Overmars, Schwarzkopf, 2000, с. 316.

Литература

  • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry // 2nd. — Springer-Verlag, 2000. — С. 307–317. — ISBN 3-540-65620-0.
  • Tomás Lozano-Pérez, Michael A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles // Communications of the ACM. — 1979. — Т. 22, вып. 10. — С. 560–570. — doi:10.1145/359156.359164.
  • S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons // Discrete & Computational Geometry. — 1997. — Т. 17, вып. 2. — С. 143–162. — ISSN 0179-5376. — doi:10.1007/BF02770871.

Ссылки