In
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 ar ...
and
robot
A robot is a machine—especially one programmable by a computer—capable of carrying out a complex series of actions automatically. A robot can be guided by an external control device, or the control may be embedded within. Robots may be c ...
motion planning, a visibility graph is a
graph of intervisible locations, typically for a set of points and obstacles in the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
. Each
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines, ...
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. When the set of locations lies in a line, this can be understood as an ordered series. Visibility graphs have therefore been extended to the realm of
time series
In mathematics, a time series is a series of data points indexed (or listed or graphed) in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. Thus it is a sequence of discrete-time data. Exa ...
analysis.
Applications
Visibility graphs may be used to find
Euclidean 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.
Two d ...
s among a set of
polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
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.
[, sections 5.1 and 5.3; .] 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 the 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 was the first general-purpose mobile robot 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 commands and break them down ...
, 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
In radio engineering, an antenna or aerial is the interface between radio waves propagating through space and electric currents moving in metal conductors, used with a transmitter or receiver. In transmission, a radio transmitter supplies a ...
, or as a tool used within
architecture
Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and constructing building ...
and
urban planning
Urban planning, also known as town planning, city planning, regional planning, or rural planning, is a technical and political process that is focused on the development and design of land use and the built environment, including air, water, ...
through
visibility graph analysis
In architecture, 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. ...
.
The visibility graph of a set of locations that lie in a line can be interpreted as a graph-theoretical representation of a time series. This particular case builds a bridge between
time series
In mathematics, a time series is a series of data points indexed (or listed or graphed) in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. Thus it is a sequence of discrete-time data. Exa ...
,
dynamical systems
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a p ...
and
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
.
Characterization
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 graph
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
s: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. It is known that not all visibility graphs induce a simple polygon. In fact, visibility graphs of simple polygons do not possess the characteristics of a few special classes of graphs.
Related problems
The
art gallery problem 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
In geometry, a bitangent to a curve is a line that touches in two distinct points and and that has the same direction as at these points. That is, is a tangent line at and at .
Bitangents of algebraic curves
In general, an algebraic cur ...
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.
[, p. 316.]
See also
*
Visibility graph analysis
In architecture, 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. ...
*
Fuzzy architectural spatial analysis
*
Space syntax
The term space syntax encompasses a set of theories and techniques for the analysis of spatial configurations. It was conceived by Bill Hillier, Julienne Hanson, and colleagues at The Bartlett, University College London in the late 1970s to ea ...
Notes
References
* .
*{{citation
, last1 = Lozano-Pérez , first1 = Tomás
, last2 = Wesley , first2 = Michael A.
, doi = 10.1145/359156.359164
, issue = 10
, journal = Communications of the ACM
, pages = 560–570
, title = An algorithm for planning collision-free paths among polyhedral obstacles
, volume = 22
, year = 1979, s2cid = 17397594
.
External links
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.
Robot control
Geometric graphs
Computational geometry