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

Пусть 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]: