Gabriel graph

In mathematics and computational geometry, the Gabriel graph of a set

Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls.

[1] For Gabriel graphs of infinite random point sets, the finite site percolation threshold gives the fraction of points needed to support connectivity: if a random subset of fewer vertices than the threshold is given, the remaining graph will almost surely have only finite connected components, while if the size of the random subset is more than the threshold, then the remaining graph will almost surely have an infinite component (as well as finite components).

[3] The Gabriel graph is a subgraph of the Delaunay triangulation.

It can be found in linear time if the Delaunay triangulation is given.

Like beta-skeletons, and unlike Delaunay triangulations, it is not a geometric spanner: for some point sets, distances within the Gabriel graph can be much larger than the Euclidean distances between points.