En matemáticas y geometría computacional , el gráfico de Gabriel de un conjunto de puntos en el plano euclidiano expresa una noción de proximidad o cercanía de esos puntos. Formalmente, es el gráfico con conjunto de vértices en el que cualquier punto y son adyacentes precisamente si son distintos, es decir , y el disco cerrado de qué segmento de línea es un diámetro que no contiene otros elementos de. Los gráficos de Gabriel se generalizan naturalmente a dimensiones más altas, con los discos vacíos reemplazados por bolas vacías cerradas . Los gráficos de Gabriel llevan el nombre de K.Ruben Gabriel , quien los presentó en un artículo con Robert R. Sokal en 1969.
Filtración
Bertin, Billiot y Drouilhet (2002) han demostrado que existe un umbral de percolación de sitio finito para los gráficos de Gabriel , y Norrenbrock (2014) ha dado valores más precisos de los umbrales de sitio y de enlace .
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 ( Matula & Sokal 1980 ).
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 .
Es una instancia de un esqueleto beta . Como los esqueletos beta, y a diferencia de las triangulaciones de Delaunay, no es una llave geométrica : para algunos conjuntos de puntos, las distancias dentro del gráfico de Gabriel pueden ser mucho mayores que las distancias euclidianas entre puntos ( Bose et al. 2006 ).
Referencias
- Bertin, Etienne; Billiot, Jean-Michel; Drouilhet, Rémy (2002), "Percolación continua en el gráfico de Gabriel", Avances en la probabilidad aplicada , 34 (4): 689–701, doi : 10.1239 / aap / 1037990948 , MR 1938937.
- Bose, Prosenjit ; Devroye, Luc ; Evans, William; Kirkpatrick, David (2006), "On the spanning ratio of Gabriel graphs and β-skeletons", SIAM Journal on Discrete Mathematics , 20 (2): 412–427, CiteSeerX 10.1.1.46.4728 , doi : 10.1137 / S0895480197318088 , MR 2257270.
- Gabriel, Kuno Ruben ; Sokal, Robert Reuven (1969), "Un nuevo enfoque estadístico para el análisis de variación geográfica", Biología Sistemática , Sociedad de Biólogos Sistemáticos, 18 (3): 259-278, doi : 10.2307 / 2412323 , JSTOR 2412323.
- Matula, David W .; Sokal, Robert Reuven (1980), "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. , 12 (3): 205–222, doi : 10.1111 / j.1538-4632.1980.tb00031.x.
- Norrenbrock, Christoph (2014), Umbral de percolación en gráficas Gabriel euclidianas planas , arXiv : 1406.0663 , Bibcode : 2014arXiv1406.0663N.