Тета-граф

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

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

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

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

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

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

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

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

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

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

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