Яо граф - Yao graph
В вычислительная геометрия, то Яо граф, названный в честь Эндрю Яо, это своего рода геометрический гаечный ключ, взвешенный неориентированный граф подключение набора геометрические точки с тем свойством, что для каждой пары точек на графике их кратчайший путь имеет длину, которая находится в постоянном коэффициенте их Евклидово расстояние.
Основная идея, лежащая в основе двумерного графа Яо, состоит в том, чтобы окружить каждую из заданных точек равномерно расположенными лучи, разбивая плоскость на сектора с равными углами, и соединяя каждую точку со своим ближайший сосед в каждом из этих секторов.[1] С графом Яо связан целочисленный параметр. k ≥ 6 это количество лучей и секторов, описанных выше; большие значения k дают более близкие приближения к евклидову расстоянию.[2] В коэффициент растяжения самое большее , куда угол секторов.[3] Ту же идею можно распространить на наборы точек более чем в двух измерениях, но количество требуемых секторов растет экспоненциально с увеличением размера.
Эндрю Яо использовали эти графики для построения многомерных Евклидовы минимальные остовные деревья.[3]
Программа для рисования графиков Яо
Смотрите также
Рекомендации
- ^ «Оверлейные сети для беспроводных систем» (PDF).
- ^ «Простые топологии» (PDF).
- ^ а б Яо, А.С. (1982), «О построении минимальных остовных деревьев в k-мерное пространство и связанные с ним проблемы », SIAM Журнал по вычислениям, 11 (4): 721–736, CiteSeerX 10.1.1.626.3161, Дои:10.1137/0211059.