Greve Gabriel

Gabriel-grafen för en uppsättning punkter i ett tvådimensionellt utrymme uttrycker begreppet närhet till dessa punkter. Formellt är detta en graf med hörn , där alla punkter och är angränsande, när de är olika, det vill säga , , och en sluten cirkel med ett segment som en diameter inte innehåller andra delar av uppsättningen .

Gabriel-grafer generaliserar naturligtvis till högre dimensioner, där tomma skivor ersätts med tomma slutna kulor . Uppkallad efter Ruben Gabriel som introducerade dem i en gemensam tidning med Robert Sokal 1969.

Läckage

Förekomsten av en ändlig nodperkolationströskel för Gabriel-grafer bevisades av Bertin, Billiot och Drouilhet [1] , medan Norrenbrock [2] gav mer exakta värden för både nod- och kanttröskelvärden (anslutnings) .

Relaterade geometriska grafer

• Gabriel-grafen är en subgraf av Delaunay-trianguleringen . Den kan hittas i linjär tid om Delaunay-trianguleringen ges [3] .

• Gabriel-grafen innehåller som undergrafer det euklidiska minimumspännande trädet , den relativa grannskapsgrafen och den närmaste granngrafen .

• Grafen är ett specialfall av betaskelettet . Liksom betaskelett och, till skillnad från Delaunay-triangulering, är denna graf inte ett geometriskt spännträd — för vissa uppsättningar punkter kan avstånden i Gabriel-grafen vara mycket större än de euklidiska avstånden mellan punkter [4] .

Anteckningar

1. ↑ Bertin, Billiot, Drouilhet, 2002 .
2. ↑ Norrenbrock, 2014 .
3. ↑ Matula, Sokal, 1980 .
4. ↑ Bose, Devroye, Evans, Kirkpatrick, 2006 .

Litteratur

• Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Kontinuerlig perkolering i Gabriel-grafen // Advances in Applied Probability. - 2002. - T. 34 , nr. 4 . — S. 689–701 . - doi : 10.1239/aap/1037990948 .
• Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. Om spännförhållandet mellan Gabriel-grafer och β-skelett // SIAM Journal on Discrete Mathematics . - 2006. - T. 20 , nej. 2 . — S. 412–427 . - doi : 10.1137/S0895480197318088 .
• Kuno Ruben Gabriel, Robert Reuven Sokal. En ny statistisk metod för geografisk variationsanalys  // Systematisk biologi . - Society of Systematic Biologists, 1969. - V. 18 , nr. 3 . — S. 259–278 . - doi : 10.2307/2412323 . — .
• David W. Matula, Robert Reuven Sokal. Egenskaper hos Gabriel-grafer som är relevanta för forskning om geografisk variation och klustring av punkter i planet // Geogr. Anal .. - 1980. - T. 12 , nr. 3 . — S. 205–222 . - doi : 10.1111/j.1538-4632.1980.tb00031.x .
• Christoph Norrenbrock. Perkolationströskel på plana euklidiska Gabriel-grafer . - 2014. - . - arXiv : 1406.0663 .