Тета-граф

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

${\displaystyle \Theta }$-графы первым описал Кларксном^[3] в 1987 и независимо Кейл^[4] в 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}\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)

См. также

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

Примечания

1. Под конусом в данном случае понимаются два луча, исходящих из точки, то есть угол.
2. Narasimhan, Smid, 2007.
3. Clarkson, 1987, с. 56–65.
4. Keil, 1988, с. 208–213.
5. Ruppert, Seidel, 1991, с. 207–210.
6. Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013, с. 109–120.
7. Bose, Morin, van Renssen, Verdonschot, 2015, с. 108–119.
8. Bonichon, Gavoille, Hanusse, Ilcinkas, 2010, с. 266–278.

Литература

• Keil J. Approximating the complete Euclidean graph // Scandinavian Workshop on Algorithm Theory (SWAT 88). — 1988. — Т. 318. — (Lecture Notes in Coputer Science (LNCS)).
• Giri Narasimhan, Michiel Smid. Geometric Spanner Networks. — Cambridge University Press, 2007. — ISBN 0-521-81513-4.
• Clarkson K. Approximation algorithms for shortest path motion planning // In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87) / Alfred V. Aho (Ed.). — New York, NY, USA: ACM, 1987.
• Ruppert J., Seidel R. Approximating the d-dimensional complete Euclidean graph // In Proc. 3rd Canad. Conf. Comput. Geom. — 1991.
• Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, André van Renssen, Sander Verdonschot. On the stretch factor of the theta-4 graph // Algorithms and data structures. — Heidelberg: Springer, 2013. — P. 109–120. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-40104-6_10.
• Prosenjit Bose, Pat Morin, André van Renssen, Sander Verdonschot. The θ₅-graph is a spanner // Computational Geometry. — 2015. — Т. 48, вып. 2. — С. 108–119. — doi:10.1016/j.comgeo.2014.08.005. — arXiv:1212.0570.
• Bonichon N., Gavoille C., Hanusse N., Ilcinkas D. Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces. // In Graph Theoretic Concepts in Computer Science. — Berlin/Heidelberg: Springer, 2010. — С. 266–278.