Тета-график

Тип геометрического гаечного ключа

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

${\displaystyle \Theta }$-графы были впервые описаны Кларксоном ^[2] в 1987 году и независимо Кейлом ^[3] в 1988 году.

Строительство

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

${\displaystyle \Theta }$-графы задаются несколькими параметрами, определяющими их построение. Наиболее очевидным параметром является , который соответствует количеству конусов с равными углами, разделяющих пространство вокруг каждой вершины. В частности, для вершины конус о можно представить как два бесконечных луча, исходящих из него с углом между ними. Что касается , мы можем обозначить эти конусы как сквозные в образце против часовой стрелки от , который обычно открывается так, что его биссектриса имеет угол 0 по отношению к плоскости. Поскольку эти конусы делят плоскость, они также делят оставшееся множество вершин графа (предполагая общее положение ) на множества через , опять же относительно . Каждая вершина графа имеет одинаковое количество конусов одной и той же ориентации, и мы можем рассмотреть множество вершин, попадающих в каждую из них. ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \theta =2\pi /k}$ ${\displaystyle p}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{k}}$ ${\displaystyle C_{1}}$ ${\displaystyle V_{1}}$ ${\displaystyle 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,q\}}$

Построение -графа возможно с помощью алгоритма прогонки по времени. ^[1] ${\displaystyle \Theta }$ ${\displaystyle O(n\log {n})}$

Характеристики

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

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

Коэффициент растяжения между любой парой точек гаечного ключа определяется как соотношение между их расстоянием в метрическом пространстве и их расстоянием внутри гаечного ключа (т. е. от следующих краев гаечного ключа). Коэффициент растяжения всего ключа — это максимальный коэффициент растяжения по всем парам точек внутри него. Вспомним выше , что тогда , когда коэффициент растяжения -графа не превышает . ^[1] Если ортогональная линия проекции в каждом конусе выбрана в качестве биссектрисы, то при коэффициент охвата не превышает . ^[4] ${\displaystyle \theta =2\pi /k}$ ${\displaystyle k\geq 9}$ ${\displaystyle \Theta }$ ${\displaystyle 1/(\cos \theta -\sin \theta )}$ ${\displaystyle l}$ ${\displaystyle k\geq 7}$ ${\displaystyle 1/(1-2\sin(\pi /k))}$

Для -граф образует граф ближайших соседей . Для легко видеть, что граф связен, поскольку каждая вершина будет соединяться с чем-то слева от нее и чем-то справа, если они существуют. Известно, что для ^[5] , ^[6] , ^[7] , ^[8] и , ^[4] -граф связен. Многие из этих результатов также дают верхние и/или нижние границы их коэффициентов охвата. ${\displaystyle k=1}$ ${\displaystyle \Theta }$ ${\displaystyle k=2}$ ${\displaystyle k=3}$ ${\displaystyle 4}$ ${\displaystyle 5}$ ${\displaystyle 6}$ ${\displaystyle \geq 7}$ ${\displaystyle \Theta }$

Когда — четное число, мы можем создать вариант -графа, известный как полуграф , где сами конусы поочередно разбиваются на четные и нечетные множества, а ребра рассматриваются только в четных конусах (или , только нечетные шишки). Известно, что полуграфы обладают некоторыми очень интересными свойствами . Например, полуграф (а, следовательно, и -граф, который представляет собой объединение двух дополнительных полуграфов ), как известно, является 2-ключом. ^[8] ${\displaystyle k}$ ${\displaystyle \Theta _{k}}$ ${\displaystyle \Theta _{k}}$ ${\displaystyle \Theta _{k}}$ ${\displaystyle \Theta _{6}}$ ${\displaystyle \Theta _{6}}$ ${\displaystyle \Theta _{6}}$

Программное обеспечение для построения тета-графиков

• Инструмент, написанный на Java
• Конусные гаечные ключи в Библиотеке алгоритмов вычислительной геометрии (CGAL)

Смотрите также

• график Яо
• Граф полу-Яо
• геометрический гаечный ключ

Рекомендации

1. Нарасимхан, Гири; Смид, Михил (2007), Geometric Spanner Networks , Cambridge University Press , ISBN 978-0-521-81513-0.
2. К. Кларксон. 1987. Аппроксимационные алгоритмы планирования движения по кратчайшему пути. В материалах девятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '87), Альфред В. Ахо (ред.). ACM, Нью-Йорк, Нью-Йорк, США, 56–65.
3. Кейл, Дж. (1988). Аппроксимация полного евклидова графа. Спецназ 88, 208–213.
4. Руперт, Дж., и Зайдель, Р. (1991). Аппроксимация d -мерного полного евклидова графа. В Proc. 3-я Канада. Конф. Вычислить. Геом (стр. 207–210).
5. Айххольцер, Освин; Пэ, Сан Вон; Барба, Луис; Бозе, Просенджит; Корман, Матиас; ван Ренссен, Андре; Таслакян, Перуз; Вердоншот, Сандер (октябрь 2014 г.), «Тета-3 связана», Computational Geometry , 47 (9): 910–917, arXiv : 1404.7186 , doi : 10.1016/j.comgeo.2014.05.001{{citation}}: CS1 maint: date and year (link)
6. Барба, Луис; Бозе, Просенджит ; Де Каруфель, Жан-Лу; ван Ренссен, Андре; Вердоншот, Сандер (2013), «О коэффициенте растяжения графа тета-4», Алгоритмы и структуры данных , Конспект лекций по информатике, том. 8037, Гейдельберг: Springer, стр. 109–120, arXiv : 1303.5473 , doi : 10.1007/978-3-642-40104-6_10 , ISBN 978-3-642-40103-9, МР  3126350.
7. Бозе, Просенджит ; Морен, Пэт ; ван Ренссен, Андре; Вердоншот, Сандер (2015), « ₅ -график θ - это гаечный ключ», Computational Geometry , 48 (2): 108–119, arXiv : 1212.0570 , doi : 10.1016/j.comgeo.2014.08.005 , MR  3260251.
8. Бонихон, Н., Гавуа, К., Ханусс, Н., и Ильчинкас, Д. (2010). Связи между тета-графами, триангуляциями Делоне и ортогональными поверхностями. В «Концепциях теории графов в информатике» (стр. 266–278). Шпрингер Берлин/Гейдельберг.