Conde gabriel

El gráfico de Gabriel de un conjunto de puntos en un espacio bidimensional expresa el concepto de proximidad de estos puntos. Formalmente, se trata de un grafo con vértices , en el que cualesquiera puntos y son contiguos, cuando son diferentes, es decir , , y un círculo cerrado con un segmento como diámetro no contiene otros elementos del conjunto .

Los gráficos de Gabriel se generalizan naturalmente a dimensiones más altas, donde los discos vacíos se reemplazan por bolas cerradas vacías . Nombrado en honor a Rubén Gabriel quien los presentó en un artículo conjunto con Robert Sokal en 1969.

Fuga

Bertin, Billiot y Drouilhet [1] demostraron la existencia de un umbral de percolación de nodo finito para los gráficos de Gabriel, mientras que Norrenbrock [2] proporcionó valores más precisos para los umbrales de nodo y borde (conexión) .

Gráficos geométricos relacionados

• El gráfico de Gabriel es un subgrafo de la triangulación de Delaunay . Se puede encontrar en tiempo lineal si se da la triangulación de Delaunay [3] .

• El gráfico de Gabriel contiene como subgráficos el árbol de expansión mínimo euclidiano , el gráfico de vecindad relativa y el gráfico de vecino más cercano .

• El gráfico es un caso especial del esqueleto beta . Al igual que los esqueletos beta y, a diferencia de la triangulación de Delaunay, este gráfico no es un árbol de expansión geométrico — para algunos conjuntos de puntos, las distancias en el gráfico de Gabriel pueden ser mucho mayores que las distancias euclidianas entre puntos [4] .

Notas

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

Literatura

• Etienne Bertin, Jean-Michel Billiot, Rémy Drouilhet. Percolación continua en el grafo de Gabriel // Avances en Probabilidad Aplicada. - 2002. - T. 34 , núm. 4 . — S. 689–701 . -doi : 10.1239 / aap/1037990948 .
• Prosenjit Bose, Luc Devroye, William Evans, David G. Kirkpatrick. Sobre la relación de expansión de los gráficos de Gabriel y los esqueletos β // SIAM Journal on Discrete Mathematics . - 2006. - T. 20 , núm. 2 . — S. 412–427 . -doi : 10.1137/ S0895480197318088 .
• Kuno Rubén Gabriel, Robert Reuven Sokal. Un nuevo enfoque estadístico para el análisis de variación geográfica  // Biología sistemática . - Sociedad de Biólogos Sistemáticos, 1969. - V. 18 , no. 3 . — S. 259–278 . -doi : 10.2307/ 2412323 . — .
• David W. Matula, Robert Reuven Sokal. Propiedades de los gráficos de Gabriel relevantes para la investigación de la variación geográfica y la agrupación de puntos en el plano // Geogr. Anal.. - 1980. - T. 12 , núm. 3 . — Pág. 205–222 . -doi : 10.1111/ j.1538-4632.1980.tb00031.x .
• Christoph Norrenbrock. Umbral de percolación en grafos planos euclidianos de Gabriel . - 2014. - . -arXiv : 1406.0663 . _