Тета-граф

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

Θ {displaystyle Theta } -графы первым описал Кларксном в 1987 и независимо Кейл в 1988.

Построение

Θ {displaystyle Theta } -графы задаются несколькими параметрами, которые определяют его построение. Наиболее очевидным параметром является k {displaystyle k} , который соответствует числу одинаковых конусов, которые разбивают пространство вокруг каждой вершины. В частности, для вершины p {displaystyle p} , конус из p {displaystyle p} можно представить как два бесконечных луча, исходящих из этой точки с углом θ = 2 π / k {displaystyle heta =2pi /k} между ними. По отношению к p {displaystyle p} мы можем пометить эти конусы как C 1 … C k {displaystyle C_{1}dots C_{k}} по часовой стрелке. Эти конусы разбивают плоскость, а также разбивают оставшееся множество вершин графа (предполагается общее положение вершин) на множества V 1 … V k , {displaystyle V_{1}dots V_{k},} снова относительно точки p {displaystyle p} . Каждая вершина графа имеет одно и то же число конусов разбиения в той же самой ориентации и мы можем рассматривать множество вершин, попавших внутрь каждого конуса.

Рассмотрим отдельный конус и нам нужно указать другой луч, исходящий из p {displaystyle p} , который мы обозначим l {displaystyle l} . Для любой вершины внутри конуса V i {displaystyle V_{i}} мы рассмотрим ортогональную проекцию каждой точки v ∈ V i {displaystyle vin V_{i}} на луч l {displaystyle l} . Пусть вершина r {displaystyle r} обладает наименьшей такой проекцией, тогда в граф добавляется ребро { p , r } {displaystyle {p,r}} . Это главное отличие от графов Яо, которые всегда выбирают ближайшую к p {displaystyle p} вершину. В примере на рисунке граф Яо включил бы ребро { p , q } {displaystyle {p,q}} .

Построение Θ {displaystyle Theta } -графа возможно с помощью заметающей прямой за время O ( n log ⁡ n ) {displaystyle O(nlog {n})} .

Свойства

Θ {displaystyle Theta } -графы показывают некоторые хорошие свойства для геометрического остова.

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

Коэффициент растяжения между любыми двумя точками остова определяется как отношение между метрическим расстоянием и расстоянием по остову (то есть следуя вдоль рёбер остова). Коэффициент растяжения всего остова равен максимальному коэффициенту растяжения по всем парам точек. Как было указано выше, θ = 2 π / k {displaystyle heta =2pi /k} , тогда, если k ⩾ 9 {displaystyle kgeqslant 9} , Θ {displaystyle Theta } -граф имеет коэффициент растяжения, не превосходящий 1 / ( cos ⁡ θ − sin ⁡ θ ) {displaystyle 1/(cos heta -sin heta )} . Если в качестве прямой l {displaystyle l} для ортогональной проекции выбирается в каждом конусе биссектриса, то для k ⩾ 7 {displaystyle kgeqslant 7} коэффициент растяжения не превосходит 1 / ( 1 − 2 sin ⁡ ( π / k ) ) {displaystyle 1/(1-2sin(pi /k))} .

Для k = 1 {displaystyle k=1} Θ {displaystyle Theta } -граф образует граф ближайших соседей. Для k = 2 {displaystyle k=2} легко видеть, что граф связен, поскольку каждая вершина связана с чем-то слева и с чем-то справа, если они существуют. Для k = 4 {displaystyle k=4} 5 {displaystyle 5} , 6 {displaystyle 6} и ⩾ 7 {displaystyle geqslant 7} известно, что Θ {displaystyle Theta } -граф связен. Есть неопубликованные результаты, показывающие, что Θ {displaystyle Theta } -графы связны также и для k = 3 {displaystyle k=3} . Есть много результатов, дающих верхнюю и/или нижнюю границу коэффициента растяжения.

Если k {displaystyle k} чётно, мы можем создать вариант Θ k {displaystyle Theta _{k}} -графа, известного как полу- Θ k {displaystyle Theta _{k}} -граф, где конусы разбиты на чётные и нечётные множества и рассматриваются рёбра только в чётных конусах (или только в нечётных). Известно, что полу- Θ k {displaystyle Theta _{k}} -графы имеют некоторые очень интересные свойства. Например, известно, что полу- Θ 6 {displaystyle Theta _{6}} -граф (и, следовательно, Θ 6 {displaystyle Theta _{6}} -граф, который является просто объединением двух дополняющих друг друга полу- Θ 6 {displaystyle Theta _{6}} -графов) являются 2-оствами.

Программы рисования тета-графов

• Программа на языке Java
• Остова на основе конусов в Библиотеке Алгоритмов Вычислительной Геометрии (Computational Geometry Algorithms Library, CGAL)