Visibility graph
From Wikipedia, the free encyclopedia
A visibility graph is a graph of intervisible locations. Each node or vertex in the graph represents a point location, and each edge represents a visible connection between them (that is, if two locations can see each other, an edge is drawn between them).
Special classes are visibility graphs for points in the plane, in particular, within a polygon. The polygon may or may not have holes (obstructions within the plan). A major open problem in this area is to characterize the visibility graphs of polygons.
In addition to theoretical problems, visibility graphs also have practical uses, for example, to calculate the placement of radio antennas, or as a tool used within architecture and urban planning through visibility graph analysis. Visibility graphs are also used in mobile robotics as a (generally offline) motion planning tool when the geometry of the environment is known, although robots have been designed that collect isovist information as they explore the environment using ultrasound sensors, which can then be turned into a visibility graph of recognisable known locations.
Contents |
[edit] 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, Springer-Verlag. ISBN 3-540-65620-0. Chapter 15: Visibility Graphs: pp.307–317.
