mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and

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 Gabriel graph of a set

S

of points in the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...

expresses one notion of proximity or nearness of those points. Formally, it is the graph

G

with vertex set

S

in which any two distinct points

p \in S

and

q \in S

are adjacent precisely when the closed disc having

pq

as a diameter contains no other points. Another way of expressing the same adjacency criterion is that

p

and

q

should be the two closest given points to their midpoint, with no other given point being as close. Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969.

Percolation

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). This threshold was proved to exist by , and more precise values of both site and bond thresholds have been given by Norrenbrock.

Related geometric graphs

The Gabriel graph is a subgraph of the Delaunay triangulation. It can be found in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

if the Delaunay triangulation is given. The Gabriel graph contains, as subgraphs, the Euclidean minimum spanning tree, the relative neighborhood graph, and the nearest neighbor graph. It is an instance of a beta-skeleton. 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.

References

{{reflist, refs= {{citation , last1 = Bertin , first1 = Etienne , last2 = Billiot , first2 = Jean-Michel , last3 = Drouilhet , first3 = Rémy , doi = 10.1239/aap/1037990948 , issue = 4 , journal = Advances in Applied Probability , mr = 1938937 , pages = 689–701 , title = Continuum percolation in the Gabriel graph , volume = 34 , year = 2002, s2cid = 121288601 {{citation , last1 = Bose , first1 = Prosenjit , author1-link = Jit Bose , last2 = Devroye , first2 = Luc , author2-link = Luc Devroye , last3 = Evans , first3 = William , last4 = Kirkpatrick , first4 = David , author4-link = David G. Kirkpatrick , doi = 10.1137/S0895480197318088 , issue = 2 , journal = SIAM Journal on Discrete Mathematics , mr = 2257270 , pages = 412–427 , title = On the spanning ratio of Gabriel graphs and β-skeletons , volume = 20 , year = 2006, citeseerx = 10.1.1.46.4728 {{citation , last1 = Gabriel , first1 = K. Ruben , author1-link = K. Ruben Gabriel , last2 = Sokal , first2 = Robert R. , author2-link = Robert R. Sokal , title = A new statistical approach to geographic variation analysis , journal = Systematic Biology , year = 1969 , pages = 259–278 , volume = 18 , doi = 10.2307/2412323 , jstor = 2412323 , issue = 3 {{citation , last1 = Matula , first1 = David W. , author1-link = David Matula , last2 = Sokal , first2 = Robert R. , author2-link = Robert R. Sokal , doi = 10.1111/j.1538-4632.1980.tb00031.x , doi-access = free , title = Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane , journal = Geographical Analysis , year = 1980 , pages = 205–222 , issue = 3 , volume = 12 {{citation , last = Norrenbrock , first = Christoph , arxiv = 1406.0663 , date = May 2016 , doi = 10.1140/epjb/e2016-60728-0 , issue = 5 , journal = European Physical Journal B , title = Percolation threshold on planar Euclidean Gabriel graphs , volume = 89, page = 111 , bibcode = 2016EPJB...89..111N , s2cid = 254114033 Euclidean plane geometry Geometric graphs