Тета-граф

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

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

Побудова

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

$\mathrm{\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\}$.

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

Властивості

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

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

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

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

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

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

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

Див. також

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

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга