In computational geometry and

robot A robot is a machine—especially one Computer program, programmable by a computer—capable of carrying out a complex series of actions Automation, automatically. A robot can be guided by an external control device, or the robot control, co ...

motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...

, a visibility graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

of intervisible locations, typically for a set of points and obstacles in the

Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...

. 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 Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

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

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 made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the 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., 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 Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...

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, 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 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 construction, constructi ...

and

urban planning Urban planning (also called city planning in some contexts) is the process of developing and designing land use and the built environment, including air, water, and the infrastructure passing into and out of urban areas, such as transportatio ...

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

dynamical systems In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space, such as in a parametric curve. Examples include the mathematical models ...

and

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

Characterization

The visibility graph of a

simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a Piecewise linear curve, piecewise-linear Jordan curve consisting of finitely many line segments. The ...

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

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. However, an efficient algorithmic characterization of the visibility graphs of simple polygons remains unknown. These graphs do not fall into many known families of well-structured graphs: they might not be

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

circle graph In graph theory, a circle graph is the intersection graph of a Chord diagram (mathematics), chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of Chord (geometry), chords of a circle such tha ...

s, or chordal graphs. An exception to this phenomenon is that the visibility graphs of simple polygons are cop-win graphs. Recognizing the visibility graph of a finite set of points in the

is complete for the existential theory of the reals.

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 , doi-access = free .

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

Applications

Characterization

Related problems

See also

Notes

References

External links