Граф Яо
Граф Яо — вид геометричного кістяка, зважений неорієнтований граф, що з'єднує множину геометричних точок, зі властивістю, що для будь-якої пари точок у графі найкоротший шлях між ними має довжину, що не перевищує на сталий множник їхньої евклідової відстані.
Названо на честь Ендрю Яо.
Опис[ред. | ред. код]
Основна ідея побудови двовимірного графа Яо полягає в оточенні кожної точки рівномірно розподіленими променями, які розбивають площину на сектори з рівними кутами, та з'єднанні кожної точки з її найближчими сусідами у кожному з цих секторів[1]. З графом Яо пов'язаний цілочисельний параметр , який дорівнює числу променів та секторів, описаних вище. Більше значення k дає точніше наближення до евклідової відстані[2]. Коефіцієнт розтягування не перевищує , де дорівнює куту секторів[3]. Цю ідею можна поширити на множини точок у розмірностях, більших від двох, але зі зростанням розмірності кількість необхідних секторів зростає експоненційно.
Ендрю Яо використав ці графи для побудови евклідових мінімальних кістякових дерев у просторах високої розмірності[3].
Програми для малювання графів Яо[ред. | ред. код]
- Кістяки на основі конусів у Бібліотеці алгоритмів обчислювальної геометрії (Computational Geometry Algorithms Library, CGAL)[Архівовано 27 березня 2019 у Wayback Machine.]
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ Overlay Networks for Wireless Systems (PDF). Архів (PDF) оригіналу за 20 листопада 2021. Процитовано 27 березня 2019.
- ↑ Simple Topologies (PDF). Архів (PDF) оригіналу за 20 листопада 2021. Процитовано 27 березня 2019.
- ↑ а б Yao, 1982, с. 721–736.
Література[ред. | ред. код]
- On constructing minimum spanning trees in k-dimensional space and related problems // SIAM Journal on Computing. — 1982. — Т. 11, вип. 4. — DOI:.