В качестве примера будет взята плоскость R2, но утверждения будут формулироваться в форме, обобщающейся на пространства более высокой размерности. В дальнейшем будем называть исходную плоскость R2 основной плоскостью.
Точку (x1, x2) будем обозначать одним вектором x, скалярное произведение x * p=x1p1 + x2p2. Если x=(x1,x2) и r - число, то запись (x, r) будет означать (x1, x2, r). Такая нотация делает очевидной обобщение на случай произвольной размерности.
Будем отображать точки из плоскости в трехмерное пространство. S - исходный набор точек.
Триангуляция Делоне
Соответствующее поднимающее отображение f: R2 -> R3 имеет вид f(x)=(x1, x2, x12 + x22). Образ f
F = { (x,z): x из R2, z=x*x }.
F - эллиптический параболоид, параболоид вращения вокруг вертикальной оси, как показано на рисунке справа.
Очевидно, все касательные плоскости к параболоиду невертикальны, а значит, делят R3 на 2 полупространства точек, расположенных сверху и снизу от плоскости.
F обладает одним важнейшим свойством. Любая невертикальная плоскость P либо не пересекает F, либо касается в одной точке, либо проекция пересечения P и F на основную плоскость является окружностью. В последнем случае часть F под плоскостью P спроектируется внутрь круга, а то, что над плоскостью - вне его. Обратно, для любой окружности в R2 существует плоскость, дающая в проекции пересечения эту окружность.
Пусть S - набор точек основной плоскости. Рассмотрим выпуклую оболочку H множества f(S). Сторону H назовем нижней стороной, если H содержется в верхнем полупространстве относительно плоскости, задаваемой этой стороной. Иначе, нижняя сторона видима наблюдателю, находящемуся очень далеко снизу, без необходимости смотреть сквозь внутренность H.
Тогда триангуляция Делоне - проекция нижних сторон H на основную плоскость.
 |
Диаграмма Вороного
Соответствующая функция отображает точку s в плоскость
Ps = { (x,z): x из R2, z = 2x*s - s*s }.
Очевидно, Ps является касательной плоскостью к рассмотренному выше параболоиду F в точке (s, s*s). Рассмотрим также поверхность
Us = { (x,z): x из R2, z = -(x-s)*(x-s) = -x*x + 2x*s - s*s }.
Для точки x базовой плоскости, вертикальная высота Us равна квадрату расстояния x до s, взятому с отрицательным знаком. Таким образом, Us - направленный вниз параболоид, касающийся основной плоскости в точке s и находящийся под основной плоскостью. Ситуация в одномерном случае показана на рисунке ниже.
 |
Если думать о Ps, Us и F как о функциях с основной плоскости на вертикальное направление, то, очевидно, Us = Ps - F. Решающим рассуждением тут является то, что F не зависит от s: для точек s, s' из S и любой точки x основной плоскости, имеем Ps(x)>Ps'(x) равносильно Us(x)>Us'(x) тогда и только тогда, когда x дальше от s, чем от s'. Аналогично, Ps(x) = Ps'(x) тогда и только тогда, когда x равноудалена от s и s'.
Итак, пусть I - пересечение замкнутых полупространств над плоскостями Ps. Тогда диаграмма Вороного V - множество проекций сторон I на основную плоскость.
Если имеется диаграмма Вороного множества из N точек на плоскости, то выпуклая оболочка этого множества может быть найдена за линейное время.
 |
Пусть диаграмма Вороного представлена РСДС(реберный список с двойными связями) с ориентацией обхода циклов, составляющих грани, например, против часовой стрелки. Будем перебирать ребра диаграммы до тех пор, пока не найдется луч (рис. выше). Если считать к ориентированным в направлении от бесконечности к его началу и при этом ячейка V(i) расположена справа от луча r, то точка рi является вершиной выпуклой оболочки. Будем просматривать ребра ячейки V(i) до тех пор, пока не встретится другой луч r'. Изменив на обратную ориентацию луча r, определим следующую вершину выпуклой оболочки pj и теперь будем просматривать ребра ячкйки Vj и т. д., пока вновь не вернемся к ячейке V(i). Ребро диаграммы просматривается лишь в том случае, если выполняется обход ребер одной из ячеек, содержащих это ребро. Так как каждое ребро принадлежит в точности двум ячейкам, то ни одно ребро не будет просмотрено более двух раз и время обработки является линейным.
8 8 8
| |
*
Обратная связь