Геометрический spanner-граф Theta: построение и свойства
Theta graph
Геометрический Theta-граф: построение на основе конусов и ближайших соседей. Свойства, применение в вычислительной геометрии и как альтернатива Yao-графу.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Тип геометрического охватывающего графа
Type of geometric spanner graph
Геометрические графы, определенные на основе ближайших соседей в секторах
geometric graphs defined from nearest neighbors in wedges
В вычислительной геометрии тета-граф, или θ-граф, является типом геометрического охватывающего графа, подобного графу Яо. Основной метод построения заключается в разделении пространства вокруг каждой вершины на набор конусов, которые, в свою очередь, разделяют остальные вершины графа. Как и графы Яо, θ-граф содержит не более одного ребра на конус; различие заключается в способе выбора этого ребра. В то время как графы Яо выбирают ближайшую вершину в соответствии с метрическим пространством графа, θ-граф определяет фиксированный луч внутри каждого конуса (обычно биссектрису конуса) и выбирает ближайшего соседа относительно ортогональных проекций на этот луч. Полученный граф обладает рядом хороших свойств охватывающего графа. θ-графы были впервые описаны Кларксоном в 1987 году и независимо Кеилом в 1988 году.
In computational geometry, the Theta graph, or graph, is a type of geometric spanner similar to a Yao graph. The basic method of construction involves partitioning the space around each vertex into a set of cones, which themselves partition the remaining vertices of the graph. Like Yao Graphs, a graph contains at most one edge per cone; where they differ is how that edge is selected. Whereas Yao Graphs will select the nearest vertex according to the metric space of the graph, the graph defines a fixed ray contained within each cone (conventionally the bisector of the cone) and selects the nearest neighbor with respect to orthogonal projections to that ray. The resulting graph exhibits several good spanner properties. graphs were first described by Clarkson in 1987 and independently by Keil in 1988.
Строительство
Графы определяются несколькими параметрами, которые определяют их построение. Наиболее очевидным параметром является *k*, который соответствует количеству конусов с равным углом, разделяющих пространство вокруг каждой вершины. В частности, для вершины *v*, конус вокруг *v* можно представить как два бесконечных луча, исходящих из неё под углом *θ* между ними. Относительно *v*, мы можем обозначить эти конусы как от 1 до *k* в направлении против часовой стрелки от некоторого опорного направления, которое обычно выбирается так, что его биссектриса образует угол 0 с плоскостью. Поскольку эти конусы разделяют плоскость, они также разделяют оставшийся набор вершин графа (при условии общего положения) на множества от 1 до *k*, опять же относительно *v*. Каждая вершина в графе получает одинаковое количество конусов в одной и той же ориентации, и мы можем рассмотреть набор вершин, попадающих в каждый конус. Рассматривая один конус, нам нужно задать дополнительный луч, исходящий из *v*, который мы обозначим *r*. Для каждой вершины *u* в графе, мы рассматриваем ортогональную проекцию каждой вершины *u* на луч *r*. Предположим, что *w* – вершина с ближайшей такой проекцией, тогда ребро (*v*, *w*) добавляется в граф. Это основное отличие от графов Яо, которые всегда выбирают ближайшую вершину; в примере изображения граф Яо включил бы ребро (*v*, *w*) вместо этого. Построение графа возможно с помощью алгоритма "sweepline" за время O(*n* log *n*). Для *k* = 1, граф образует граф ближайших соседей. Для *k* = 2, легко увидеть, что граф связен, так как каждая вершина будет соединена с чем-то слева от неё и с чем-то справа, если они существуют. Для *k* = 3, 4 и 5, граф, как известно, связен. Многие из этих результатов также дают верхние и/или нижние границы для их коэффициентов растяжения. Когда *k* – чётное число, мы можем создать вариант графа, известный как полуграф, где сами конусы разделены на чётные и нечётные множества в чередующемся порядке, а рёбра рассматриваются только в чётных конусах (или только в нечётных конусах). Полуграфы, как известно, обладают некоторыми очень хорошими свойствами. Например, полуграф (и, следовательно, граф, который является просто объединением двух дополнительных полуграфов) известен как 2-спаннер.
graphs are specified with a few parameters which determine their construction. The most obvious parameter is , which corresponds to the number of equal angle cones that partition the space around each vertex. In particular, for a vertex , a cone about can be imagined as two infinite rays emanating from it with angle between them. With respect to , we can label these cones as through in a counterclockwise pattern from , which conventionally opens so that its bisector has angle 0 with respect to the plane. As these cones partition the plane, they also partition the remaining vertex set of the graph (assuming general position) into the sets through , again with respect to Every vertex in the graph gets the same number of cones in the same orientation, and we can consider the set of vertices that fall into each. Considering a single cone, we need to specify another ray emanating from , which we will label For every vertex in , we consider the orthogonal projection of each onto Suppose that is the vertex with the closest such projection, then the edge is added to the graph. This is the primary difference from Yao Graphs which always select the nearest vertex; in the example image, a Yao Graph would include the edge instead. Construction of a graph is possible with a sweepline algorithm in time. For , the graph forms a nearest neighbor graph. For , it is easy to see that the graph is connected, as each vertex will connect to something to its left, and something to its right, if they exist. For , , , and , the graph is known to be connected. Many of these results also give upper and/or lower bounds on their spanning ratios. When is an even number, we can create a variant of the graph known as the half graph, where the cones themselves are partitioned into even and odd sets in an alternating fashion, and edges are only considered in the even cones (or, only the odd cones). Half graphs are known to have some very nice properties of their own. For example, the half graph (and, consequently, the graph, which is just the union of two complementary half graphs) is known to be a 2 spanner.