Gabriel graph

From Wikipedia, the free encyclopedia

Points a and b are Gabriel neighbours, as c is outside their diameter circle.

The presence of point c within the circle prevents points a and b from being Gabriel neighbors.

A Gabriel graph is a certain graph that connects a set of points in the Euclidean plane. Two points P and Q are connected by an edge in the Gabriel graph whenever the disk having line segment PQ as its diameter contains no other points from the given point set. More generally, in any dimension, the Gabriel graph connects any two points forming the endpoints of the diameter of an empty sphere. Gabriel graphs are named after K. R. Gabriel, who introduced them in a paper with R. R. Sokal in 1969.

The Gabriel graph is a subgraph of the Delaunay triangulation; it can be found in linear time if the Delaunay triangulation is given (Matula and Sokal, 1980). The Gabriel graph contains as a subgraph the Euclidean minimum spanning tree and the nearest neighbor graph. It is an instance of a beta-skeleton.

[edit] References

Gabriel, K. R. & Sokal, R. R. (1969), “A new statistical approach to geographic variation analysis”, Systematic Zoology 18: 259–270, DOI 10.2307/2412323 .

Matula, D. W. & Sokal, R. R. (1980), “Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane”, Geogr. Anal. 12: 205–222 .