Тета-граф

Тета-граф или $\mathrm{\Theta }$-graph — вид геометрического остова, подобного графу Яо. Основной метод построения разбивает пространство вокруг каждой вершины на множество углов, которые тем самым разбивают оставшиеся вершины графа. Подобно графам Яо $\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)$ рёбер.

Шаблон:Не переведено 5 между любыми двумя точками остова определяется как отношение между метрическим расстоянием и расстоянием по остову (то есть следуя вдоль рёбер остова). Коэффициент растяжения всего остова равен максимальному коэффициенту растяжения по всем парам точек. Как было указано выше, $\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)

См. также

• Граф Яо
• Геометрический остов

Литература

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