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

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

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