Граф Яо

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

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

Основна ідея побудови двовимірного графа Яо полягає в оточенні кожної точки рівномірно розподіленими променями, які розбивають площину на сектори з рівними кутами, та з'єднанні кожної точки з її найближчими сусідами у кожному з цих секторів^[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.]

• Тета-граф
• Граф напів-Яо^[en]

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