“Gabriel graph”的意思、由来-开放百科全书

词条

Gabriel graph

释义

Percolation
Related geometric graphs
References

In mathematics and computational geometry, the Gabriel graph of a set of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set in which any points and are adjacent precisely if they are distinct, i.e. , and the closed disc of which line segment is a diameter contains no other elements of . 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

A finite site percolation threshold for Gabriel graphs has been proven to exist by {{harvtxt|Bertin|Billiot|Drouilhet|2002}}, and more precise values of both site and bond thresholds have been given by {{harvtxt|Norrenbrock|2014}}.

Related geometric graphs

The Gabriel graph is a subgraph of the Delaunay triangulation. It can be found in linear time if the Delaunay triangulation is given {{harv|Matula|Sokal|1980}}.

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 {{harv|Bose|Devroye|Evans|Kirkpatrick|2006}}.

References

{{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}}.

{{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 = Kuno Ruben | last2 = Sokal | first2 = Robert Reuven
| author1-link = Kuno Ruben Gabriel | author2-link = Robert Reuven 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
| publisher = Society of Systematic Biologists}}.

{{citation

| doi = 10.1111/j.1538-4632.1980.tb00031.x
| last1 = Matula | first1 = David W. | last2 = Sokal | first2 = Robert Reuven
| author2-link = Robert Reuven Sokal
| title = Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane
| journal = Geogr. Anal.
| year = 1980
| pages = 205–222
| issue = 3
| volume = 12}}.

{{citation

| last = Norrenbrock | first = Christoph
| arxiv = 1406.0663
| title = Percolation threshold on planar Euclidean Gabriel Graphs
| year = 2014| bibcode = 2014arXiv1406.0663N}}.

2 : Euclidean plane geometry|Geometric graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。