Тета-граф

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

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

Побудова

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

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

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

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

Властивості

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

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

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

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

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

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

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

Див. також

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

Література

• 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. — ISBN 0-521-81513-4.
• 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 (4 квітня). — С. 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.