Visibility graph

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

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.

ee also

*Art gallery problem

References

* cite book|author=O'Rourke, J.
authorlink = Joseph O'Rourke (professor)
year=1987|title=Art Gallery Theorems and Algorithms|publisher=Oxford University Press|id=ISBN 0-19-503965-3
* Chapter 15: Visibility Graphs: pp.307–317.

External links

oftware

* [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.]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Visibility graph analysis — (VGA) is a method of analysing the inter visibility connections within buildings or urban networks. Visibility graph analysis was developed from the architectural theory of space syntax by Turner et al (2001), and is applied through construction… …   Wikipedia

  • Visibility (geometry) — Visibility is a mathematical abstraction of the real life notion of visibility.Given a set of obstacles in the Euclidean space, two points in the space are said to be visible to each other, if the line segment that joins them does not intersect… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… …   Wikipedia

  • Outerplanar graph — A maximal outerplanar graph and its 3 coloring. In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing.… …   Wikipedia

  • Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… …   Wikipedia

  • Constraint graph (layout) — In some tasks of integrated circuit layout design a necessity arises to optimize placement of non overlapping objects in the plane. In general this problem is extremely hard, and to tackle it with computer algorithms, certain assumptions are made …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Scene graph — A scene graph is a general data structure commonly used by vector based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.The scene… …   Wikipedia

  • Crown graph — Crown graphs with six, eight, and ten vertices. In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j. The crown… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”