Editing Visibility graph

{{short description|Graph of intervisible locations in computational geometry}}
In [[computational geometry]] and [[robot]] [[motion planning]],<ref>{{Cite journal|last1=Niu|first1=Hanlin|last2=Savvaris|first2=Al|last3=Tsourdos|first3=Antonios|last4=Ji|first4=Ze|date=2019|title=Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles|url=https://orca.cardiff.ac.uk/118170/1/Voronoi-Visibility%20Roadmap-based%20Path%20Planning%20Algorithm%20for%20Unmanned%20Su.._.pdf|journal=Journal of Navigation|volume=72|issue=4|pages=850–874|doi=10.1017/S0373463318001005|s2cid=67908628 |issn=0373-4633}}</ref> a '''visibility graph''' is a [[Graph (discrete mathematics)|graph]] of intervisible locations, typically for a set of points and obstacles in the [[Euclidean plane]].  Each [[vertex (graph theory)|node]] in the graph represents a point location, and each [[graph theory|edge]] represents a [[visible connection]] between them. That is, if the line segment connecting two locations does not pass through any obstacle, an edge is drawn between them in the graph. When the set of locations lies in a line, this can be understood as an ordered series. Visibility graphs have therefore been extended to the realm of [[time series]] analysis.

==Applications==
Visibility graphs may be used to find [[Euclidean shortest path]]s among a set of [[polygon]]al obstacles in the plane: the shortest path between two obstacles follows straight line segments except at the [[vertex (geometry)|vertices]] of the obstacles, where it may turn, so the Euclidean shortest path is the shortest path in a visibility graph that has as its nodes the start and destination points and the [[vertex (geometry)|vertices]] of the obstacles.<ref name="robot">{{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}, sections 5.1 and 5.3; {{harvtxt|Lozano-Pérez|Wesley|1979}}.</ref> Therefore, the Euclidean shortest path problem may be decomposed into two simpler subproblems: constructing the visibility graph, and applying a shortest path algorithm such as [[Dijkstra's algorithm]] to the graph. For planning the motion of a robot that has non-negligible size compared to the obstacles, a similar approach may be used after expanding the obstacles to compensate for the size of the robot.<ref name="robot"/> {{harvtxt|Lozano-Pérez|Wesley|1979}} attribute the visibility graph method for Euclidean shortest paths to research in 1969 by [[Nils Nilsson (researcher)|Nils Nilsson]] on motion planning for [[Shakey the robot]], and also cite a 1973 description of this method by Russian mathematicians M. B. Ignat'yev, F. M. Kulakov, and A. M. Pokrovskiy.

Visibility graphs may also be used to calculate the placement of [[Antenna (radio)|radio antennas]], or as a tool used within [[architecture]] and [[urban planning]] through [[visibility graph analysis]].

The visibility graph of a set of locations that lie in a line can be interpreted as a graph-theoretical representation of a time series.<ref>{{cite journal |last1=Lacasa |first1=Lucas |last2=Luque |first2=Bartolo |last3=Ballesteros |first3=Fernando |last4=Luque |first4=Jordi |last5=Nuño |first5=Juan Carlos |title=From time series to complex networks: The visibility graph |journal=Proceedings of the National Academy of Sciences |date=2008 |volume=105 |issue=13 |pages=4972–4975 |doi=10.1073/pnas.0709247105|pmid=18362361 |pmc=2278201 |arxiv=0810.0920 |doi-access=free |bibcode=2008PNAS..105.4972L }}</ref> This particular case builds a bridge between [[time series]], [[dynamical systems]] and [[graph theory]].

==Characterization==
The visibility graph of a [[simple polygon]] has the polygon's vertices as its point locations, and the exterior of the polygon as the only obstacle. Visibility graphs of simple polygons must be [[Hamiltonian graph]]s: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. It is known that not all visibility graphs induce a simple polygon. However, an efficient algorithmic characterization of the visibility graphs of simple polygons remains unknown. These graphs do not fall into many known families of well-structured graphs: they might not be [[perfect graph]]s, [[circle graph]]s, or [[chordal graph]]s.<ref>{{Cite journal|title = On recognizing and characterizing visibility graphs of simple polygons|journal = Discrete & Computational Geometry|date = 1997-03-01|issn = 0179-5376|pages = 143–162|volume = 17|issue = 2|doi = 10.1007/BF02770871|first = S. K.|last = Ghosh|doi-access = free}}</ref> An exception to this phenomenon is that the visibility graphs of simple polygons are [[cop-win graph]]s.<ref>{{cite journal
 | last1 = Lubiw | first1 = Anna | author1-link = Anna Lubiw
 | last2 = Snoeyink | first2 = Jack
 | last3 = Vosoughpour | first3 = Hamideh
 | arxiv = 1601.01298
 | doi = 10.1016/j.comgeo.2017.07.001
 | journal = [[Computational Geometry (journal)|Computational Geometry]]
 | mr = 3693353
 | pages = 14–27
 | title = Visibility graphs, dismantlability, and the cops and robbers game
 | volume = 66
 | year = 2017}}</ref>

==Related problems==
The [[art gallery problem]] is the problem of finding a small set of points such that all other non-obstacle points are visible from this set. Certain forms of the art gallery problem may be interpreted as finding a [[dominating set]] in a visibility graph.

The [[bitangent]]s of a system of polygons or curves are lines that touch two of them without penetrating them at their points of contact. The bitangents of a set of polygons form a subset of the visibility graph that has the polygon's vertices as its nodes and the polygons themselves as the obstacles. The visibility graph approach to the Euclidean shortest path problem may be sped up by forming a graph from the bitangents instead of using all visibility edges, since a Euclidean shortest path may only enter or leave the boundary of an obstacle along a bitangent.<ref>{{harvtxt|de Berg|van Kreveld|Overmars|Schwarzkopf|2000}}, p. 316.</ref>

==See also==

*[[Visibility graph analysis]]
*[[Fuzzy architectural spatial analysis]]
*[[Space syntax]]

==Notes==
{{reflist}}

==References==
* {{citation
 | last1 = de Berg
 | first1 = Mark
 | last2 = van Kreveld
 | first2 = Marc
 | last3 = Overmars
 | first3 = Mark
 | author3-link = Mark Overmars
 | last4 = Schwarzkopf
 | first4 = Otfried
 | contribution = Chapter 15: Visibility Graphs
 | edition = 2nd
 | isbn = 978-3-540-65620-3
 | pages = [https://archive.org/details/computationalgeo00berg/page/307 307–317]
 | publisher = [[Springer-Verlag]]
 | title = Computational Geometry
 | year = 2000
 | url-access = registration
 | url = https://archive.org/details/computationalgeo00berg/page/307
 }}.
*{{citation
 | last1 = Lozano-Pérez | first1 = Tomás
 | last2 = Wesley | first2 = Michael A.
 | doi = 10.1145/359156.359164
 | issue = 10
 | journal = Communications of the ACM
 | pages = 560–570
 | title = An algorithm for planning collision-free paths among polyhedral obstacles
 | volume = 22
 | year = 1979| s2cid = 17397594
 | doi-access = free
 }}.

== External links ==
*[http://www.VisiLibity.org VisiLibity: A free open source C++ library of floating-point visibility algorithms and supporting data types.  This software can be used for calculating visibility graphs of polygonal environments with polygonal holes.  A Matlab interface is also included.]

[[Category:Robot control]]
[[Category:Geometric graphs]]
[[Category:Computational geometry]]