Conde yao

Graph Yao  es un tipo de gráfico ponderado no dirigido de expansión geométrica que conecta un conjunto de puntos geométricos con la propiedad de que para cualquier par de puntos en el gráfico, el camino más corto entre ellos tiene una longitud que no excede su distancia euclidiana por un factor constante .

El nombre de Andrew Yao .

Descripción

La idea principal de construir un gráfico de Yao bidimensional es rodear cada punto con rayos distribuidos uniformemente , dividiendo el plano en sectores con ángulos iguales y conectando cada punto con sus vecinos más cercanos en cada uno de estos sectores [1] . Un parámetro entero está asociado con el gráfico de Yao , que es igual al número de rayos y sectores descritos anteriormente. Un valor mayor de k da una aproximación más precisa a la distancia euclidiana [2] . El factor de estiramiento no excede , donde es igual al ángulo de los sectores [3] . La misma idea se puede extender a conjuntos de puntos en dimensiones mayores que dos, 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ínimos euclidianos en espacios de alta dimensión [3] .

Programas de dibujo gráfico Yao

Véase también

Notas

  1. ↑ Redes superpuestas para sistemas inalámbricos . Consultado el 27 de marzo de 2019. Archivado desde el original el 20 de noviembre de 2021.
  2. ↑ Topologías simples . Consultado el 27 de marzo de 2019. Archivado desde el original el 20 de noviembre de 2021.
  3. ↑ 1 2 Yao, 1982 , pág. 721–736.

Literatura