Граф Яо

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

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

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