Граф Яо
Граф Яо — вид геометрического остова, взвешенный неориентированный граф, соединяющий множество геометрических точек со свойством, что для любой пары точек в графе кратчайший путь между ними имеет длину не превосходящую на постоянный множитель их евклидова расстояния.
Назван в честь Эндрю Яо.
Описание
Основная идея построения двухмерного графа Яо заключается в окружении каждой точки равномерно распределёнными лучами, разбивая плоскость на сектора с равными углами, и соединении каждой точки с её ближайшими соседями в каждом из этих секторов[1]. С графом Яо связан целочисленный параметр [math]\displaystyle{ k \geqslant 6 }[/math], который равен числу лучей и секторов, описанных выше. Большее значение k даёт более точное приближение к евклидову расстоянию[2]. Коэффициент растяжения не превосходит [math]\displaystyle{ 1/(\cos \theta - \sin \theta) }[/math], где [math]\displaystyle{ \theta }[/math] равен углу секторов[3]. Та же идея может быть распространена на множества точек в размерностях, больших двух, но число требуемых секторов растёт экспоненциально с ростом размерности.
Эндрю Яо использовал эти графы, чтобы строить евклидовы минимальные остовные деревья в пространствах высокой размерности[3].
Программы рисования графов Яо
- Остова на основе конусов в Библиотеке Алгоритмов Вычислительной Геометрии (Computational Geometry Algorithms Library, CGAL) Архивная копия от 27 марта 2019 на Wayback Machine
См. также
Примечания
- ↑ Overlay Networks for Wireless Systems . Дата обращения: 27 марта 2019. Архивировано 20 ноября 2021 года.
- ↑ Simple Topologies . Дата обращения: 27 марта 2019. Архивировано 20 ноября 2021 года.
- ↑ 3,0 3,1 Yao, 1982, с. 721–736.
Литература
- On constructing minimum spanning trees in k-dimensional space and related problems // SIAM Journal on Computing. — 1982. — Т. 11, вып. 4. — doi:10.1137/0211059.
Для улучшения этой статьи желательно: |