Grafo de Yao (Yao Graph, YG)

El Grafo de Yao, YG_k(V) , con k ≥ 4 , es el grafo que resulta de unir cada nodo v de la nube de puntos de R² con el nodo más cercano de cada uno de los k-sectores en que queda dividido el plano al trazar k semirrectas con origen el punto v y equi-espaciadas angularmente con un ángulo de 2π / k .

 

 

Ilustración Aristas del grafo de Yao, con k=6, y Grafo de Yao

 

Propiedad 1: El Grafo de Yao de un conjunto de puntos S del plano contiene al  árbol generador mínimo de S.

Propiedad 2: Si θ = 2π / k con k > 6, entonces el Grafo de Yao es un grafo con una dilación 1 / (1 – 2sen (θ/ 2)).