Тета-граф

Тета-граф або ${\displaystyle \Theta }$-граф — вид геометричного кістяка, подібний до графа Яо. За основного методу побудови простір навколо кожної вершини розбивається на множину кутів, які тим самим розбивають решту вершин графа. Подібно до графів Яо ${\displaystyle \Theta }$-граф містить максимум одне ребро на конус (для вибраної вершини), а відрізняються вони способом вибору ребра. Тоді як у графі Яо вибирають найближчу вершину відповідно до метрики простору, у ${\displaystyle \Theta }$-графі визначають фіксований промінь, що міститься в кожному конусі (зазвичай це бісектриса кута), і вибирають найближчого сусіда відповідно до ортогональної проєкції на цей промінь. Отриманий граф показує деякі хороші властивості кістякового графа.

${\displaystyle \Theta }$-графи першим описав Кларксон (1987) та незалежно Кейл (1988).

Побудова

Приклад конуса ${\displaystyle \Theta }$-графа, що виходить з точки ${\displaystyle p}$ з прямою ортогональних проєкцій ${\displaystyle l}$

${\displaystyle \Theta }$-графи задають декількома параметрами, що визначають їх побудову. Найочевиднішим параметром є ${\displaystyle k}$, що відповідає числу однакових конусів, на які розбито простір навколо кожної вершини. Зокрема, для вершини ${\displaystyle p}$, конус із ${\displaystyle p}$ можна уявити як два нескінченних промені, що виходять із цієї точки з кутом ${\displaystyle \theta =2\pi /k}$ між ними. Пов'язані з точкою ${\displaystyle p}$ конуси можна позначити як ${\displaystyle C_{1}\dots C_{k}}$ за годинниковою стрілкою. Ці конуси розбивають площину, а також розбивають решту вершин графа (передбачається загальне положення вершин) на множини ${\displaystyle V_{1}\dots V_{k},}$ знову відносно точки ${\displaystyle p}$. Кожна вершина графа має те саме число конусів розбиття в тій самій орієнтації і ми можемо розглядати множини вершин, що потрапили всередину кожного з конусів.

Розглянемо окремий конус: потрібно вказати ще один промінь, що виходить з ${\displaystyle p}$, який позначимо ${\displaystyle l}$. Для будь-якої вершини всередині конуса ${\displaystyle V_{i}}$ ми знайдемо ортогональну проєкцію кожної точки ${\displaystyle v\in V_{i}}$ на промінь ${\displaystyle l}$. Нехай вершина ${\displaystyle r}$ має найменшу таку проєкцію, тоді до графа додається ребро ${\displaystyle \{p,r\}}$. Це головна відмінність від графів Яо, в яких завжди вибирають найближчу до ${\displaystyle p}$ вершину. У прикладі на малюнку до графа Яо увійшло б ребро ${\displaystyle \{p,q\}}$.

Можна побудувати ${\displaystyle \Theta }$-графа за допомогою замітання прямою за час ${\displaystyle O(n\log {n})}$ .

Властивості

${\displaystyle \Theta }$-графи показують деякі хороші властивості геометричного кістяка.

Коли параметр ${\displaystyle k}$ — сталий, ${\displaystyle \Theta }$-граф є розрідженим кістяком. Кожен конус дає максимум одне ребро, більшість вершин матиме малий степінь і весь граф матиме не більше ${\displaystyle k\cdot n=O(n)}$ ребер.

^[en] між будь-якими двома точками кістяка визначається як відношення між метричною відстанню і відстанню за кістяком (тобто вздовж ребер кістяка). Коефіцієнт розтягу всього кістяка дорівнює найбільшому коефіцієнту розтягу за всіма парами точок. Як було зазначено вище, ${\displaystyle \theta =2\pi /k}$, тоді, якщо ${\displaystyle k\geqslant 9}$, ${\displaystyle \Theta }$-граф має коефіцієнт розтягу, що не перевищує ${\displaystyle 1/(\cos \theta -\sin \theta )}$. Якщо як промінь ${\displaystyle l}$ для ортогональної проєкції вибирається в кожному конусі бісектриса, то для ${\displaystyle k\geqslant 7}$ коефіцієнт розтягу не перевищує ${\displaystyle 1/(1-2\sin(\pi /k))}$.

При ${\displaystyle k=1}$ ${\displaystyle \Theta }$-граф утворює граф найближчих сусідів. При ${\displaystyle k=2}$ легко бачити, що граф зв'язний, оскільки кожна вершина пов'язана з чимось ліворуч і з чимось праворуч, якщо вони існують. Для ${\displaystyle k=4}$, ${\displaystyle 5}$, ${\displaystyle 6}$ та ${\displaystyle \geqslant 7}$ відомо, що ${\displaystyle \Theta }$-граф зв'язний. Є неопубліковані результати, що показують, що ${\displaystyle \Theta }$-графи зв'язні також і для ${\displaystyle k=3}$. Є багато результатів, що дають верхню та/або нижню межу коефіцієнта розтягу.

Якщо ${\displaystyle k}$ парне, можна створити варіант ${\displaystyle \Theta _{k}}$-графа, відомого як напів-${\displaystyle \Theta _{k}}$-граф, де конуси розбито на парні і непарні множини і розглядаються ребра тільки в парних конусах (або тільки в непарних). Відомо, що напів-${\displaystyle \Theta _{k}}$-графи мають деякі дуже цікаві властивості. Наприклад, відомо, що напів-${\displaystyle \Theta _{6}}$-граф (і, отже, ${\displaystyle \Theta _{6}}$-граф, який є просто об'єднанням двох напів-${\displaystyle \Theta _{6}}$-графів, що доповняльнюють один одного) є 2-кістяками.

Програми для малювання тета-графів

• Програма мовою Java
• Кістяки на основі конусів у Бібліотеці алгоритмів обчислювальної геометрії (Computational Geometry Algorithms Library, CGAL)

Див. також

• Граф Яо
• Геометричний кістяк

Примітки

1. Під конусом тут розуміють два промені, які виходять із точки, тобто кут.
2. Narasimhan, Smid, 2007.
3. Clarkson, 1987, с. 56–65.
4. Keil, 1988, с. 208–213.
5. Ruppert, Seidel, 1991, с. 207–210.
6. Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013, с. 109–120.
7. Bose, Morin, van Renssen, Verdonschot, 2015, с. 108–119.
8. Bonichon, Gavoille, Hanusse, Ilcinkas, 2010, с. 266–278.

Література

• Keil J. Approximating the complete Euclidean graph // Scandinavian Workshop on Algorithm Theory (SWAT 88). — 1988. — Т. 318. — (Lecture Notes in Coputer Science (LNCS))
• Giri Narasimhan, Michiel Smid. Geometric Spanner Networks. — Cambridge University Press, 2007. — .
• Clarkson K. Approximation algorithms for shortest path motion planning // In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87). — New York, NY, USA : ACM, 1987.
• Ruppert J., Seidel R. Approximating the d-dimensional complete Euclidean graph // In Proc. 3rd Canad. Conf. Comput. Geom. — 1991.
• Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot. On the stretch factor of the theta-4 graph // Algorithms and data structures. — Heidelberg : Springer, 2013. — Т. 8037. — P. 109–120. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-40104-6_10.
• Prosenjit Bose, Pat Morin, André van Renssen, Sander Verdonschot. The θ₅-graph is a spanner // Computational Geometry. — 2015. — Т. 48, вип. 2 (24 червня). — С. 108–119. — arXiv:1212.0570. — DOI:10.1016/j.comgeo.2014.08.005.
• Bonichon N., Gavoille C., Hanusse N., Ilcinkas D. Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. // In Graph Theoretic Concepts in Computer Science. — Berlin/Heidelberg : Springer, 2010. — С. 266–278.