Граф Яо

Граф Яо — вид геометрического остова, взвешенный неориентированный граф, соединяющий множество геометрических точек со свойством, что для любой пары точек в графе кратчайший путь между ними имеет длину не превосходящую на постоянный множитель их евклидова расстояния.

Назван в честь Эндрю Яо.

ОписаниеПравить

Основная идея построения двухмерного графа Яо заключается в окружении каждой точки равномерно распределёнными лучами, разбивая плоскость на сектора с равными углами, и соединении каждой точки с её ближайшими соседями в каждом из этих секторов. С графом Яо связан целочисленный параметр $k⩾<!--\; ⩾\; -->6$$k\geqslant 6$ , который равен числу лучей и секторов, описанных выше. Большее значение k даёт более точное приближение к евклидову расстоянию. Коэффициент растяжения не превосходит $1/(\cos <!--\; \; -->\mathrm{\theta <!--\; \theta \; -->}-<!--\; -\; -->\sin <!--\; \; -->\mathrm{\theta <!--\; \theta \; -->})$$1/(\cos \theta -\sin \theta )$ , где $\mathrm{\theta <!--\; \theta \; -->}$$\theta$  равен углу секторов. Та же идея может быть распространена на множества точек в размерностях, больших двух, но число требуемых секторов растёт экспоненциально с ростом размерности.

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

Программы рисования графов ЯоПравить

• Остова на основе конусов в Библиотеке Алгоритмов Вычислительной Геометрии (Computational Geometry Algorithms Library, CGAL) Архивная копия от 27 марта 2019 на Wayback Machine

См. такжеПравить

• Тета-граф
• Полуяов граф^[en]

ЛитератураПравить

• On constructing minimum imgning trees in k-dimensional space and related problems // SIAM Journal on Computing. — 1982. — Т. 11, вып. 4. — doi:10.1137/0211059.