Граф Яо — вид геометрического остова, взвешенный неориентированный граф, соединяющий множество геометрических точек со свойством, что для любой пары точек в графе кратчайший путь между ними имеет длину не превосходящую на постоянный множитель их евклидова расстояния.
Назван в честь Эндрю Яо.
Описание Основная идея построения двухмерного графа Яо заключается в окружении каждой точки равномерно распределёнными лучами, разбивая плоскость на сектора с равными углами, и соединении каждой точки с её ближайшими соседями в каждом из этих секторов. С графом Яо связан целочисленный параметр , который равен числу лучей и секторов, описанных выше. Большее значение даёт более точное приближение к евклидову расстоянию. Коэффициент растяжения не превосходит , где равен углу секторов. Та же идея может быть распространена на множества точек в размерностях, больших двух, но число требуемых секторов растёт экспоненциально с ростом размерности.
Эндрю Яо использовал эти графы, чтобы строить евклидовы минимальные остовные деревья в пространствах высокой размерности.
Программы рисования графов Яо Остова на основе конусов в Библиотеке Алгоритмов Вычислительной Геометрии (Computational Geometry Algorithms Library, CGAL)
См. также Тета-граф
Примечания
Литература
Категория:Вычислительная геометрия Категория:Геометрическая теория графов