Grafo de Yao

En geometría computacional, el grafo de Yao, llamado así por Andrew Chi-Chih Yao, es un tipo de extensor geométrico, un grafo ponderado que conecta un conjunto de puntos geométricos con la propiedad de que, para cada par de puntos en el grafo, su camino más corto tiene una longitud que está dentro de un factor constante de su distancia euclídea.

Concepto

La idea básica del grafo de Yao bidimensional es rodear cada uno de los puntos dados con rayos igualmente espaciados, dividiendo el plano en sectores con ángulos iguales, y conectar cada punto con su vecino más cercano en cada uno de estos sectores. Asociado a un grafo de Yao está un parámetro entero k ≥ 6 que es el número de rayos y sectores descritos anteriormente. Valores mayores de k producen aproximaciones más cercanas a la distancia euclídea. El factor de estiramiento es como máximo ${\displaystyle 1/(\cos \theta -\sin \theta )}$, donde ${\displaystyle \theta }$ es el ángulo de los sectores. La misma idea se puede extender a conjuntos de puntos en más de dos dimensiones, pero el número de sectores necesarios crece exponencialmente con la dimensión.

Andrew Chi-Chih Yao utilizó estos grafos para construir árboles de extensión mínima euclídea de alta dimensión.

Software para dibujar grafos de Yao

• Cone-based Spanners in Computational Geometry Algorithms Library (CGAL)

Véase también

• Grafo theta
• Semigrafo de Yao

Referencias