Планарные геометрические остовы: различия между версиями

Предположим, что каждое ребро (u, v) графа G реализовано в видео отрезка прямой, соединяющей точки u и v. Граф G называется [[планарный граф|плоским]], если его ребра пересекаются только в точках их общих вершин.

Задача 1. Определить наименьшее вещественное число t > 1, для которого выполняется следующее утверждение:

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

Задача 2. Определить наименьшее целое положительное число D, для которого выполняется следующее утверждение:

Существует константное значение t, такое, что для каждого множества S из n точек на плоскости существует плоский граф с множеством вершин S и максимальной степенью, не превышающей D, который является t-остовом для S. Разработать эффективный алгоритм построения такого плоского t-остова.

Левкопулос и Лингас [14] обобщили результат теоремы 1: Предположим, что дана триангуляция Делоне для множества S. Тогда для любого вещественного числа r > 0 за время O(n) можно построить плоский граф G с множеством вершин S, являющийся t-остовом для S, где <math>t = (1 + 1/r) 4 \pi \sqrt{3}/9</math>, совокупная длина ребер которого будет не более чем в 2r + 1 раз превышать вес остовного дерева для S.

'''Теорема 2. Пусть S – конечное множество точек на плоскости. Рассмотрим триангуляцию Делоне для S, основанную на выпуклой функции расстояния, определяемой при помощи равностороннего треугольника. Этот плоский граф является 2-остовом для S (в котором длины путей измеряются при помощи евклидовой метрики).'''