Тета-граф (Mymg-ijgs)

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

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

Построение

Пример конуса $\Theta$ -графа, исходящего из точки $p$ с прямой ортогональных проекций $l$

$\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\}$ .

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

Свойства

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

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

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

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

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

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

См. также

Примечания

↑ Под конусом в данном случае понимаются два луча, исходящих из точки, то есть угол.
↑ ¹ ² ³ Narasimhan, Smid, 2007.
↑ Clarkson, 1987, с. 56–65.
↑ Keil, 1988, с. 208–213.
↑ ¹ ² Ruppert, Seidel, 1991, с. 207–210.
↑ Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013, с. 109–120.
↑ Bose, Morin, van Renssen, Verdonschot, 2015, с. 108–119.
↑ ¹ ² 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.

[1] Под конусом в данном случае понимаются два луча, исходящих из точки, то есть угол.

[_2f5a4f750311f4ab-2] ¹ ² ³ Narasimhan, Smid, 2007.

[_6cf6543a7ec72554-3] Clarkson, 1987, с. 56–65.

[_e5428172ace3b6cd-4] Keil, 1988, с. 208–213.

[_cd9aac8935684e98-5] ¹ ² Ruppert, Seidel, 1991, с. 207–210.

[_4ec1397139ddbfc3-6] Barba, Bose, De Carufel, van Renssen, Verdonschot, 2013, с. 109–120.

[_10124b3a16a50ddc-7] Bose, Morin, van Renssen, Verdonschot, 2015, с. 108–119.

[_dd045f4d3368c016-8] ¹ ² Bonichon, Gavoille, Hanusse, Ilcinkas, 2010, с. 266–278.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]