Русская Википедия:Тета-граф
Тета-граф или <math>\Theta</math>-graph — вид геометрического остова, подобного графу Яо. Основной метод построения разбивает пространство вокруг каждой вершины на множество углов, которые тем самым разбивают оставшиеся вершины графа. Подобно графам Яо <math>\Theta</math>-граф содержит максимум одно ребро на конус[1] (для выбранной вершины), а отличаются они способом выбора ребра. В то время как графы Яо выбирают ближайшую вершину согласно метрике пространства, <math>\Theta</math>-граф определяет фиксированный луч, содержащийся в каждом конусе (обычно используется биссектриса угла) и выбирается ближайший сосед согласно ортогональной проекции на этот луч. Получающийся граф показывает некоторые хорошие свойства остовного графаШаблон:Sfn.
<math>\Theta</math>-графы первым описал КларксномШаблон:Sfn в 1987 и независимо КейлШаблон:Sfn в 1988.
Построение
<math>\Theta</math>-графы задаются несколькими параметрами, которые определяют его построение. Наиболее очевидным параметром является <math>k</math>, который соответствует числу одинаковых конусов, которые разбивают пространство вокруг каждой вершины. В частности, для вершины <math>p</math>, конус из <math>p</math> можно представить как два бесконечных луча, исходящих из этой точки с углом <math>\theta = 2\pi/k</math> между ними. По отношению к <math>p</math> мы можем пометить эти конусы как <math>C_1 \dots C_k</math> по часовой стрелке. Эти конусы разбивают плоскость, а также разбивают оставшееся множество вершин графа (предполагается общее положение вершин) на множества <math>V_1 \dots V_k,</math> снова относительно точки <math>p</math>. Каждая вершина графа имеет одно и то же число конусов разбиения в той же самой ориентации и мы можем рассматривать множество вершин, попавших внутрь каждого конуса.
Рассмотрим отдельный конус и нам нужно указать другой луч, исходящий из <math>p</math>, который мы обозначим <math>l</math>. Для любой вершины внутри конуса <math>V_i</math> мы рассмотрим ортогональную проекцию каждой точки <math>v \in V_i</math> на луч <math>l</math>. Пусть вершина <math>r</math> обладает наименьшей такой проекцией, тогда в граф добавляется ребро <math>\{p,r\}</math>. Это главное отличие от графов Яо, которые всегда выбирают ближайшую к <math>p</math> вершину. В примере на рисунке граф Яо включил бы ребро <math>\{p,q\}</math>.
Построение <math>\Theta</math>-графа возможно с помощью заметающей прямой за время <math>O(n \log{n})</math>Шаблон:Sfn.
Свойства
<math>\Theta</math>-графы показывают некоторые хорошие свойства для геометрического остова.
Когда параметр <math>k</math> является константой, <math>\Theta</math>-граф является разреженным остовом. Каждый конус даёт максимум одно ребро, большинство вершин будет иметь малую степень и весь граф будет иметь не более <math>k \cdot n = O(n)</math> рёбер.
Шаблон:Не переведено 5 между любыми двумя точками остова определяется как отношение между метрическим расстоянием и расстоянием по остову (то есть следуя вдоль рёбер остова). Коэффициент растяжения всего остова равен максимальному коэффициенту растяжения по всем парам точек. Как было указано выше, <math>\theta = 2\pi/k</math>, тогда, если <math>k \geqslant 9</math>, <math>\Theta</math>-граф имеет коэффициент растяжения, не превосходящий <math>1/(\cos\theta - \sin\theta)</math>Шаблон:Sfn. Если в качестве прямой <math>l</math> для ортогональной проекции выбирается в каждом конусе биссектриса, то для <math>k \geqslant 7</math> коэффициент растяжения не превосходит <math>1/(1 - 2\sin(\pi / k))</math>Шаблон:Sfn.
Для <math>k = 1</math> <math>\Theta</math>-граф образует граф ближайших соседей. Для <math>k = 2</math> легко видеть, что граф связен, поскольку каждая вершина связана с чем-то слева и с чем-то справа, если они существуют. Для <math>k = 4</math>Шаблон:Sfn <math>5</math>Шаблон:Sfn, <math>6</math>Шаблон:Sfn и <math>\geqslant 7</math>Шаблон:Sfn известно, что <math>\Theta</math>-граф связен. Есть неопубликованные результаты, показывающие, что <math>\Theta</math>-графы связны также и для <math>k = 3</math>. Есть много результатов, дающих верхнюю и/или нижнюю границу коэффициента растяжения.
Если <math>k</math> чётно, мы можем создать вариант <math>\Theta_k</math>-графа, известного как полу-<math>\Theta_k</math>-граф, где конусы разбиты на чётные и нечётные множества и рассматриваются рёбра только в чётных конусах (или только в нечётных). Известно, что полу-<math>\Theta_k</math>-графы имеют некоторые очень интересные свойства. Например, известно, что полу-<math>\Theta_6</math>-граф (и, следовательно, <math>\Theta_6</math>-граф, который является просто объединением двух дополняющих друг друга полу-<math>\Theta_6</math>-графов) являются 2-оствамиШаблон:Sfn.
Программы рисования тета-графов
- Программа на языке Java
- Остова на основе конусов в Библиотеке Алгоритмов Вычислительной Геометрии (Computational Geometry Algorithms Library, CGAL)
См. также
Примечания
Литература
- ↑ Под конусом в данном случае понимаются два луча, исходящих из точки, то есть угол.
