Тета-график - Theta graph

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

${ displaystyle Theta}$ -графы были впервые описаны Кларксоном^[2] в 1987 году и независимо Кейлом^[3] в 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}}$ через ${ displaystyle C_ {k}}$ по схеме против часовой стрелки от ${ displaystyle C_ {1}}$ , который условно открывается так, что его биссектриса имеет угол 0 по отношению к плоскости. Поскольку эти конусы разделяют плоскость, они также разделяют оставшееся множество вершин графа (при условии, что общая позиция ) в множества ${ 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 {п, г }}$ добавляется к графику. Это основное отличие от Yao Graphs, которые всегда выбирают ближайшую вершину; в примере изображения График Яо будет включать край ${ displaystyle {p, q }}$ вместо.

Строительство ${ displaystyle Theta}$ -граф возможен с алгоритм Sweepline в ${ Displaystyle О (п журнал {п})}$ время.^[1]

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

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

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

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

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

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

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

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

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

^ ^а ^б ^c Нарасимхан, Гири; Smid, Michiel (2007), Геометрические гаечные сети, Издательство Кембриджского университета, ISBN 0-521-81513-4.
^ К. Кларксон. 1987. Аппроксимационные алгоритмы для планирования движения по кратчайшему пути. В материалах девятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '87), Альфред В. Ахо (ред.). ACM, Нью-Йорк, Нью-Йорк, США, 56–65.
^ Кейл, Дж. (1988). Аппроксимация полного евклидова графа. SWAT 88, 208–213.
^ ^а ^б Рупперт Дж. И Зайдель Р. (1991). Приближая d-мерный полный евклидов граф. В Proc. 3-я канадская. Конф. Comput. Геом (стр. 207–210).
^ Освин Айхольцер, Санг Вон Бэ, Луис Барба, Просенджит Бозе, Матиас Корман, Андре ван Ренссен, Перуз Таслакян, Сандер (2014). Тета-3 подключена. In Computational Geometry: Theory and Applications (volume 47, Issue 9, October 2014, Pages 910-917). https://doi.org/10.1016/j.comgeo.2014.05.001
^ Барба, Луис; Бозе, Просенджит; Де Каруфель, Жан-Лу; ван Ренссен, Андре; Вердоншот, Сандер (2013), «О факторе растяжения графа тета-4», Алгоритмы и структуры данных, Конспект лекций по информатике, 8037, Heidelberg: Springer, стр. 109–120, arXiv:1303.5473, Дои:10.1007/978-3-642-40104-6_10, Г-Н 3126350.
^ Бозе, Просенджит; Морен, Пат; ван Ренссен, Андре; Вердоншот, Сандер (2015), «θ₅-граф - гаечный ключ », Вычислительная геометрия, 48 (2): 108–119, arXiv:1212.0570, Дои:10.1016 / j.comgeo.2014.08.005, Г-Н 3260251.
^ ^а ^б Бонишон, Н., Гавой, К., Ханусс, Н., и Ильсинкас, Д. (2010). Связь между тета-графами, триангуляциями Делоне и ортогональными поверхностями. В теоретических концепциях графов в компьютерных науках (стр. 266–278). Springer Berlin / Heidelberg.

[gsgs-1] а ^б ^c Нарасимхан, Гири; Smid, Michiel (2007), Геометрические гаечные сети, Издательство Кембриджского университета, ISBN 0-521-81513-4.

[1987clarkson-2] К. Кларксон. 1987. Аппроксимационные алгоритмы для планирования движения по кратчайшему пути. В материалах девятнадцатого ежегодного симпозиума ACM по теории вычислений (STOC '87), Альфред В. Ахо (ред.). ACM, Нью-Йорк, Нью-Йорк, США, 56–65.

[1988keil-3] Кейл, Дж. (1988). Аппроксимация полного евклидова графа. SWAT 88, 208–213.

[ruppertseidel1991-4] а ^б Рупперт Дж. И Зайдель Р. (1991). Приближая d-мерный полный евклидов граф. В Proc. 3-я канадская. Конф. Comput. Геом (стр. 207–210).

[aichholzer_etal-5] Освин Айхольцер, Санг Вон Бэ, Луис Барба, Просенджит Бозе, Матиас Корман, Андре ван Ренссен, Перуз Таслакян, Сандер (2014). Тета-3 подключена. In Computational Geometry: Theory and Applications (volume 47, Issue 9, October 2014, Pages 910-917). https://doi.org/10.1016/j.comgeo.2014.05.001

[6] Барба, Луис; Бозе, Просенджит; Де Каруфель, Жан-Лу; ван Ренссен, Андре; Вердоншот, Сандер (2013), «О факторе растяжения графа тета-4», Алгоритмы и структуры данных, Конспект лекций по информатике, 8037, Heidelberg: Springer, стр. 109–120, arXiv:1303.5473, Дои:10.1007/978-3-642-40104-6_10, Г-Н 3126350.

[7] Бозе, Просенджит; Морен, Пат; ван Ренссен, Андре; Вердоншот, Сандер (2015), «θ₅-граф - гаечный ключ », Вычислительная геометрия, 48 (2): 108–119, arXiv:1212.0570, Дои:10.1016 / j.comgeo.2014.08.005, Г-Н 3260251.

[bonichon_etal-8] а ^б Бонишон, Н., Гавой, К., Ханусс, Н., и Ильсинкас, Д. (2010). Связь между тета-графами, триангуляциями Делоне и ортогональными поверхностями. В теоретических концепциях графов в компьютерных науках (стр. 266–278). Springer Berlin / Heidelberg.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]