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

Пусть S – конечном множество точек на плоскости, имеющих общее положение; т.е. никакие три точки из S не лежат на одной прямой и никакие четыре – на одной окружности. Триангуляцией Делоне для множества S является плоский граф с множеством вершин S, в котором (u, v) является ребром в том и только том случае, если существует окружность, проходящая через u и v, внутри которой не содержится ни одной точки S. (Поскольку точки S находятся в общем положении, этот гарф представляет собой триангуляцию). Триангуляция Делоне на множестве из n точек на плоскости может быть построена за время O(n log n). Добкин, Фридман и Суповит [10] первыми показали, что коэффициент растяжения триангуляции Делоне ограничен константой. Они доказали, что триангуляция Делоне является t-остовом для t = л (1 + p5)/2. Наилучшую известную на данный момент верхнюю границу коэффициента растяжения для этого графа предложили Кил и Гутвин [12]:

Теорема 1. Пусть S – конечное множество точек на плоскости. Триангуляция Делоне для множества S является t-остовом S при t = 4л.

Несколько более строгий результат был доказан Бозе и др. [3]. Они доказали, что для любых двух точек p и q из S триангуляция Делоне содержит путь между p и q, длина которого не превышает {Ал p3/9) |pq|, а длина каждого ребра на этом пути не превышает |pq|.

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

Триангуляцию Делоне можно иначе определить как двойственную конструкцию по отношению к диаграмме Вороного на множестве S. Рассматривая диаграмму Вороного для метрики, отличной от евклидовой, получаем соответствующую триангуляцию Делоне. Чу [7] показал, что триангуляция Делоне на основе манхэттенского расстояния представляет собой p10-остов (в этом остове длины путей измеряются при помощи евклидовой метрики). Чу [8] также дал наилучшее известное на сегодня решение задачи 1:

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