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

1/(\cos \theta - \sin \theta)

, where

\theta

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.

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)

References

{{DEFAULTSORT:Yao Graph Computational geometry Geometric graph theory

Software for drawing Yao graphs

See also

References