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

-графы первым описал Кларксном в 1987 и независимо Кейл в 1988.

Построение

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

Рассмотрим отдельный конус и нам нужно указать другой луч, исходящий из , который мы обозначим . Для любой вершины внутри конуса мы рассмотрим ортогональную проекцию каждой точки на луч . Пусть вершина обладает наименьшей такой проекцией, тогда в граф добавляется ребро . Это главное отличие от графов Яо, которые всегда выбирают ближайшую к вершину. В примере на рисунке граф Яо включил бы ребро .

Построение -графа возможно с помощью заметающей прямой за время .

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

Когда параметр является константой, -граф является разреженным остовом. Каждый конус даёт максимум одно ребро, большинство вершин будет иметь малую степень и весь граф будет иметь не более рёбер.

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

Для -граф образует граф ближайших соседей. Для легко видеть, что граф связен, поскольку каждая вершина связана с чем-то слева и с чем-то справа, если они существуют. Для , и известно, что -граф связен. Есть неопубликованные результаты, показывающие, что -графы связны также и для . Есть много результатов, дающих верхнюю и/или нижнюю границу коэффициента растяжения.

Если чётно, мы можем создать вариант -графа, известного как полу--граф, где конусы разбиты на чётные и нечётные множества и рассматриваются рёбра только в чётных конусах (или только в нечётных). Известно, что полу--графы имеют некоторые очень интересные свойства. Например, известно, что полу--граф (и, следовательно, -граф, который является просто объединением двух дополняющих друг друга полу--графов) являются 2-оствами.

Программы рисования тета-графов Программа на языке Java Остова на основе конусов в Библиотеке Алгоритмов Вычислительной Геометрии (Computational Geometry Algorithms Library, CGAL)

См. также Граф Яо Геометрический остов

Примечания

Литература

Категория:Вычислительная геометрия Категория:Геометрическая теория графов