En geometría computacional , el gráfico de Yao , llamado así por Andrew Yao , es un tipo de llave geométrica , un gráfico ponderado no dirigido que conecta un conjunto de puntos geométricos con la propiedad de que, para cada par de puntos en el gráfico, su camino más corto tiene una longitud que está dentro de un factor constante de su distancia euclidiana .
La idea básica que subyace al gráfico de Yao bidimensional es rodear cada uno de los puntos dados por 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. [1] Asociado a un gráfico de Yao hay 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 euclidiana. [2] El factor de estiramiento es como máximo , donde es el ángulo de los sectores. [3] La misma idea se puede extender a conjuntos de puntos en más de dos dimensiones, pero el número de sectores requeridos crece exponencialmente con la dimensión.
Andrew Yao utilizó estos gráficos para construir árboles de expansión mínimos euclidianos de alta dimensión . [3]
