Visibility graph
In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each 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.
Visibility graphs may be used to find Euclidean shortest paths among a set of polygonal obstacles in the plane: the shortest path between two obstacles follows straight line segments except at the 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 vertices of the obstacles (Lozano-Pérez & Wesley 1979).
Visibility graphs may also be used to calculate the placement of radio antennas, or as a tool used within architecture and urban planning through visibility graph analysis.
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 graphs: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. However, the precise characterization of these graphs is unknown. It is a major open problem in this area whether there exists a polynomial time algorithm that can take as input a graph (possibly together with a fixed Hamiltonian in the cycle that is to correspond to the boundary) and produce as output a polygon for which it is the visibility graph, if such a polygon exists.
See also
References
- O'Rourke, J. (1987). Art Gallery Theorems and Algorithms. Oxford University Press. ISBN 0-19-503965-3.
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0.
{{cite book}}:|edition=has extra text (help)CS1 maint: multiple names: authors list (link) Chapter 15: Visibility Graphs: pp.307–317. - Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "An algorithm for planning collision-free paths among polyhedral obstacles", Communications of the ACM, 22 (10): 560–570, doi:10.1145/359156.359164.