Visibility graph
Encyclopedia
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.
s among a set of polygon
al 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. 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 this size of the robot. attribute the visibility graph method for Euclidean shortest paths to research in 1969 by 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 radio antennas
, or as a tool used within architecture
and urban planning
through visibility graph analysis
.
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.
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.
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
and robot
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
, a visibility graph is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
in the graph represents a point location, and each edge
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 a collection of edges that connect pairs of...
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.
Applications
Visibility graphs may be used to find Euclidean shortest pathEuclidean shortest path
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles....
s among a set of polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
al obstacles in the plane: the shortest path between two obstacles follows straight line segments except at the vertices
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
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
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
of the obstacles. 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
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
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 this size of the robot. attribute the visibility graph method for Euclidean shortest paths to research in 1969 by Nils Nilsson on motion planning for Shakey the robot
Shakey the Robot
Shakey the Robot was the first general-purpose mobile robot to be able to reason about its own actions. While other robots would have to be instructed on each individual step of completing a larger task, Shakey could analyze the command and break it down into basic chunks by itself...
, 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 radio antennas
Antenna (radio)
An antenna is an electrical device which converts electric currents into radio waves, and vice versa. It is usually used with a radio transmitter or radio receiver...
, or as a tool used within architecture
Architecture
Architecture is both the process and product of planning, designing and construction. Architectural works, in the material form of buildings, are often perceived as cultural and political symbols and as works of art...
and urban planning
Urban planning
Urban planning incorporates areas such as economics, design, ecology, sociology, geography, law, political science, and statistics to guide and ensure the orderly development of settlements and communities....
through visibility graph analysis
Visibility graph analysis
Visibility graph analysis 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...
.
Characterization
The visibility graph of a simple polygonSimple polygon
In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....
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.
Related problems
The art gallery problemArt gallery problem
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards which together can observe the whole gallery...
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
Dominating set
In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
in a visibility graph.
The bitangent
Bitangent
In mathematics, a bitangent to a curve C is a line L that touches C in two distinct points P and Q and that has the same direction to C at these points...
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.
External links
See also
- Visibility graph analysisVisibility graph analysisVisibility graph analysis 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...
- Fuzzy architectural spatial analysisFuzzy architectural spatial analysisFuzzy architectural spatial analysis is a spatial analysis method of analyzing the spatial formation and architectural space intensity within any architectural organization.Fuzzy architectural spatial analysis is used in architecture, interior design, urban planning and...
- Space syntaxSpace syntaxThe term space syntax encompasses a set of theories and techniques for the analysis of spatial configurations. Originally it was conceived by Bill Hillier, Julienne Hanson and colleagues at The Bartlett, University College London in the late 1970s to early 1980s as a tool to help architects...