Grafo de Gabriel

En geometría computacional, el grafo de Gabriel es un grafo que expresa una idea de proximidad de un conjunto S de puntos del plano Euclídeo. El grafo de Gabriel toma su nombre del matemático K. Ruben Gabriel, quién los introdujo en un artículo junto a Robert Sokal en 1969.

Formalmente, es el grafo cuyos vértices son los puntos de S en el que dos puntos P y Q son adyacentes si son distintos y el disco cerrado cuyo diámetro es el segmento de línea PQ no contiene otros elementos de S. Los grafos de Gabriel se pueden generalizar a dimensiones más altas, reemplazando los discos vacíos por bolas cerradas.

• 
  Los puntos a y b son vecinos de Gabriel, si ningún punto c es interior al círculo de diámetro ab.
• 
  La presencia del punto c dentro del círculo impide que a y b puedan ser marcados como vecinos en el Grafo de Gabriel.

Propiedades

• El grafo de Gabriel es un grafo plano, es decir, puede ser dibujado en el plano sin que ninguna arista se cruce.
• El grafo de Gabriel es un subgrafo de la triangulación de Delaunay.
• El grafo de Gabriel puede ser calculado en tiempo lineal a partir de la triangulación de Delaunay.
• El grafo de Gabriel contiene como subgrafos al árbol recubridor mínimo, al grafo de vecindad relativa, y al grafo del vecino más cercano.
• Es un caso de un beta-esqueleto. Al igual que los beta-esqueletos, y a diferencia de las triangulaciones de Delaunay, no es un recubrimiento geométrico, ya que existen conjuntos de puntos cuyas distancias medidas dentro del grafo de Gabriel pueden ser mucho mayores que las distancias euclidianas entre los puntos
• Existe un umbral de percolación para los grafos de Gabriel de conjuntos de puntos finitos.

Referencias