Contele Gabriel

Graficul Gabriel al unui set de puncte dintr -un spațiu bidimensional exprimă conceptul de proximitate a acestor puncte. Formal, acesta este un grafic cu vârfuri , în care orice puncte și sunt adiacente, atunci când sunt diferite, adică , și un cerc închis cu un segment ca diametru nu conține alte elemente ale mulțimii . $S$ $G$ $S$ $p\în S$ $q\în S$ $p\neq q$ ${\overline {pq)}$ $S$

Graficele Gabriel se generalizează în mod natural la dimensiuni mai mari, unde discurile goale sunt înlocuite cu bile închise goale . Numit după Ruben Gabriel , care le-a prezentat într-o lucrare comună cu Robert Sokal în 1969.

Scurgere

Existența unui prag finit de percolare a nodului pentru graficele Gabriel a fost dovedită de Bertin, Billiot și Drouilhet [1] , în timp ce Norrenbrock [2] a dat valori mai precise atât pentru pragurile de nod, cât și pentru marginea (conexiune) .

Grafice geometrice înrudite

Graficul Gabriel este un subgraf al triangulației Delaunay . Poate fi găsită în timp liniar dacă este dată triangulația Delaunay [3] .

Graficul Gabriel conține ca subgrafe arborele de întindere minim euclidian , graficul de vecinătate relativă și cel mai apropiat grafic vecin .

Graficul este un caz special al scheletului beta . La fel ca scheletele beta și, spre deosebire de triangulația Delaunay, acest grafic nu este un arbore de întindere geometric — pentru unele seturi de puncte, distanțele din graficul Gabriel pot fi mult mai mari decât distanțele euclidiene dintre puncte [4] .

Note

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

Literatură

Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Percolarea continuului în graficul Gabriel // Progrese în probabilitatea aplicată. - 2002. - T. 34 , nr. 4 . — S. 689–701 . - doi : 10.1239/aap/1037990948 .
Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. Despre raportul de acoperire al graficelor Gabriel și al scheletelor β // SIAM Journal on Discrete Mathematics . - 2006. - T. 20 , nr. 2 . — S. 412–427 . - doi : 10.1137/S0895480197318088 .
Kuno Ruben Gabriel, Robert Reuven Sokal. O nouă abordare statistică a analizei variației geografice // Biologie sistematică . - Societatea Biologilor Sistematici, 1969. - V. 18 , nr. 3 . — S. 259–278 . - doi : 10.2307/2412323 . — .
David W. Matula, Robert Reuven Sokal. Proprietăți ale graficelor Gabriel relevante pentru cercetarea variației geografice și gruparea punctelor în plan // Geogr. Anal .. - 1980. - T. 12 , nr. 3 . — S. 205–222 . - doi : 10.1111/j.1538-4632.1980.tb00031.x .
Christoph Norrenbrock. Pragul de percolare pe graficele planare euclidiene Gabriel . - 2014. - . - arXiv : 1406.0663 .