Тета-график

Эта статья посвящена геометрическим графам, определенным из ближайших соседей в клиньях. Информацию о тета-графах в теории графов (три пути с общими конечными точками) см. в Глоссарии теории графов .

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

$\Theta$-графы были впервые описаны Кларксоном. в 1987 году и независимо Кейлом в 1988 году.

Строительство

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

$\Theta$-графы задаются несколькими параметрами, определяющими их построение. Наиболее очевидным параметром является $k$, что соответствует количеству конусов с равными углами, разделяющих пространство вокруг каждой вершины. В частности, для вершины $p$, конус около $p$ можно представить как два бесконечных луча, исходящих из него под углом $\theta =2\pi /k$ между ними. Что касается $p$, мы можем обозначить эти конусы как $C_{1}$ через $C_{k}$ по схеме против часовой стрелки от $C_{1}$, который условно открывается так, что его биссектриса имеет угол 0 по отношению к плоскости. Поскольку эти конусы делят плоскость, они также делят оставшееся множество вершин графа (предполагая общее положение ) на множества $V_{1}$ через $V_{k}$, опять же относительно $p$. Каждая вершина графа имеет одинаковое количество конусов одной и той же ориентации, и мы можем рассмотреть множество вершин, попадающих в каждую из них.

Рассматривая один конус, нам нужно указать еще один луч, исходящий из $p$, который мы обозначим $l$. Для каждой вершины в $V_{i}$, мы рассматриваем ортогональную проекцию каждого $v\in V_{i}$ на $l$. Предположим, что $r$ — вершина с ближайшей такой проекцией, то ребро $\{p,r\}$ добавляется на график. Это основное отличие от графов Яо, которые всегда выбирают ближайшую вершину; в примере изображения график Яо будет включать ребро $\{p,q\}$ вместо.

Строительство $\Theta$-график возможен с помощью алгоритма развертки в $O(n\log {n})$ время.

Характеристики

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

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

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

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

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

Программное обеспечение для построения тета-графиков

• Инструмент, написанный на Java
• Конусные гаечные ключи в Библиотеке алгоритмов вычислительной геометрии (CGAL)

См. также

• график Яо
• Граф полу-Яо
• геометрический гаечный ключ