Яо граф - Yao graph

В вычислительная геометрия, то Яо граф, названный в честь Эндрю Яо, это своего рода геометрический гаечный ключ, взвешенный неориентированный граф подключение набора геометрические точки с тем свойством, что для каждой пары точек на графике их кратчайший путь имеет длину, которая находится в постоянном коэффициенте их Евклидово расстояние.

Основная идея, лежащая в основе двумерного графа Яо, состоит в том, чтобы окружить каждую из заданных точек равномерно расположенными лучи, разбивая плоскость на сектора с равными углами, и соединяя каждую точку со своим ближайший сосед в каждом из этих секторов.^[1] С графом Яо связан целочисленный параметр. k ≥ 6 это количество лучей и секторов, описанных выше; большие значения k дают более близкие приближения к евклидову расстоянию.^[2] В коэффициент растяжения самое большее ${\displaystyle 1/(\cos \theta -\sin \theta )}$, куда ${\displaystyle \theta }$ угол секторов.^[3] Ту же идею можно распространить на наборы точек более чем в двух измерениях, но количество требуемых секторов растет экспоненциально с увеличением размера.

Эндрю Яо использовали эти графики для построения многомерных Евклидовы минимальные остовные деревья.^[3]

Программа для рисования графиков Яо

• Конические гаечные ключи в библиотеке алгоритмов вычислительной геометрии (CGAL)

Смотрите также

• Тета-график
• Полу-Яо график

Рекомендации

1. «Оверлейные сети для беспроводных систем» (PDF).
2. «Простые топологии» (PDF).
3. Яо, А.С. (1982), «О построении минимальных остовных деревьев в k-мерное пространство и связанные с ним проблемы », SIAM Журнал по вычислениям, 11 (4): 721–736, CiteSeerX  10.1.1.626.3161, Дои:10.1137/0211059.