En matemáticas y geometría computacional , el grafo 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 grafo con un conjunto de vértices en el que dos puntos distintos y son adyacentes precisamente cuando el disco cerrado que tiene como diámetro no contiene otros puntos. Otra forma de expresar el mismo criterio de adyacencia es que y deben ser los dos puntos dados más cercanos a su punto medio , sin que ningún otro punto dado esté tan cerca. Los grafos de Gabriel se generalizan naturalmente a dimensiones superiores, con los discos vacíos reemplazados por bolas cerradas vacías . Los grafos de Gabriel reciben su nombre de K. Ruben Gabriel , quien los introdujo en un artículo con Robert R. Sokal en 1969. [1]
Para los grafos de Gabriel de conjuntos de puntos aleatorios infinitos, el umbral de percolación de sitio finito proporciona la fracción de puntos necesaria para soportar la conectividad: si se proporciona un subconjunto aleatorio de menos vértices que el umbral, el grafo restante casi seguramente tendrá solo componentes conectados finitos, mientras que si el tamaño del subconjunto aleatorio es mayor que el umbral, entonces el grafo restante casi seguramente tendrá un componente infinito (así como componentes finitos). Bertin, Billiot y Drouilhet (2002) demostraron la existencia de este umbral [2] , y Norrenbrock ha proporcionado valores más precisos tanto de los umbrales de sitio como de enlace [3] .
El grafo 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. [4]
El gráfico de Gabriel contiene, como subgrafos, el árbol de expansión mínimo euclidiano , el gráfico de vecindad relativa y el gráfico de vecino más cercano .
Se trata de un ejemplo de esqueleto beta . Al igual que 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. [5]
