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 ...
, the Yao graph, named after
Andrew Yao
Andrew Chi-Chih Yao (; born December 24, 1946) is a Chinese computer scientist and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Yao use ...
, is a kind of
geometric spanner
A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path ...
, a weighted
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
connecting a set of
geometric points with the property that, for every pair of points in the graph, their
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between tw ...
has a length that is within a constant factor of their
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
.
The basic idea underlying the two-dimensional Yao graph is to surround each of the given points by equally spaced
rays
Ray may refer to:
Fish
* Ray (fish), any cartilaginous fish of the superorder Batoidea
* Ray (fish fin anatomy), a bony or horny spine on a fin
Science and mathematics
* Ray (geometry), half of a line proceeding from an initial point
* Ray (gra ...
, partitioning the plane into sectors with equal angles, and to connect each point to its
nearest neighbor in each of these sectors. Associated with a Yao graph is an integer parameter which is the number of rays and sectors described above; larger values of produce closer approximations to the Euclidean distance.
The
stretch factor
The stretch factor (i.e., bilipschitz constant) of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space is embedded into another metric space by a metric map, a continuous one-to-one functi ...
is at most
, where
is the angle of the sectors.
The same idea can be extended to point sets in more than two dimensions, but the number of sectors required grows exponentially with the dimension.
Andrew Yao
Andrew Chi-Chih Yao (; born December 24, 1946) is a Chinese computer scientist and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences (IIIS) at Tsinghua University. Yao use ...
used these graphs to construct high-dimensional
Euclidean minimum spanning tree
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments ...
s.
[.]
Software for drawing Yao graphs
Cone-based Spanners in Computational Geometry Algorithms Library (CGAL)
See also
*
Theta graph
*
Semi-Yao graph
References
{{DEFAULTSORT:Yao Graph
Computational geometry
Geometric graph theory