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

Несколько более строгий результат был получен Бозе и др. [3]. Они доказали, что для любых двух точек p и q из S триангуляция Делоне содержит путь между p и q, длина которого не превышает <math>t = 4 \pi \sqrt{3} / 9 \; |pq|</math>, а длина каждого ребра на этом пути не превышает |pq|.

Левкопулос и Лингас [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.