En geometría computacional , el gráfico Yao , que lleva el nombre de Andrew Yao , es una especie de llave geométrica , un gráfico no dirigido ponderado que conecta un conjunto de puntos geométricos con la propiedad de que, por 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 a su vecino más cercano en cada uno de estos sectores. [1] Asociado con 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, dónde 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 usó estos gráficos para construir árboles de expansión mínima euclidiana de alta dimensión . [3]
Software para dibujar gráficos de Yao
Ver también
Referencias
- ^ "Redes superpuestas para sistemas inalámbricos" (PDF) .
- ^ "Topologías simples" (PDF) .
- ^ a b Yao, AC (1982), "Sobre la construcción de árboles de expansión mínimos en el espacio k -dimensional y problemas relacionados", SIAM Journal on Computing , 11 (4): 721–736, CiteSeerX 10.1.1.626.3161 , doi : 10.1137 / 0211059.