Тета-граф

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

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

${\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})}$^[2] .

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

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

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

При ${\displaystyle k=1}$ ${\displaystyle \Theta }$-граф утворює граф найближчих сусідів. При ${\displaystyle k=2}$ легко бачити, що граф зв'язний, оскільки кожна вершина пов'язана з чимось ліворуч і з чимось праворуч, якщо вони існують. Для ${\displaystyle k=4}$^[6], ${\displaystyle 5}$^[7], ${\displaystyle 6}$^[8] та ${\displaystyle \geqslant 7}$^[5] відомо, що ${\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-кістяками^[8].

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

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