Visibility graph

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).

Visibility graphs are classically regarded as two dimensional artefacts. They are drawn within a plan of a site, or in mathematical terms, a polygon. The polygon may or may not have holes (obstructions within the plan).

O'Rourke (1987) writes about various Art Gallery Theorems, where the plan is of a supposed art gallery. For the purposes of mathematics, an art gallery is simply an arbitrary polygon with or without holes, so they do not tend to look like plans of art galleries on the page; instead, they allow investigation into various art gallery problems. One art gallery problem considered by O'Rourke was raised by Klee in 1973. Klee asked: how many guards does it take to guard an art gallery?

The problem can be set for both polygons with or without holes.

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) path-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.

References