Gráfico de Yao

En geometría computacional , el grafo de Yao , que recibe su nombre de Andrew Yao , es una especie de conector geométrico , un grafo no dirigido 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 euclidiana .

La idea básica subyacente al 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. ^{[ 1 ]} 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 euclidiana. ^{[ 2 ]} El factor de estiramiento es como máximo${\displaystyle 1/(\cos \theta -\sin \theta )}$, dónde${\displaystyle \theta }$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 grafos para construir árboles de expansión mínima euclidianos de alta dimensión . ^{[ 3 ]}

• Conectores basados ​​en conos en la biblioteca de algoritmos de geometría computacional (CGAL)

• Gráfico Theta
• Gráfico Semi-Yao