В качестве примера будет взята плоскость R², но утверждения будут формулироваться в форме, обобщающейся на пространства более высокой размерности. В дальнейшем будем называть исходную плоскость R² основной плоскостью.

Точку (x₁, x₂) будем обозначать одним вектором x, скалярное произведение x * p=x₁p₁ + x₂p₂. Если x=(x₁,x₂) и r - число, то запись (x, r) будет означать (x₁, x₂, r). Такая нотация делает очевидной обобщение на случай произвольной размерности.

Будем отображать точки из плоскости в трехмерное пространство. S - исходный набор точек.

Соответствующее поднимающее отображение f: R² -> R³ имеет вид f(x)=(x₁, x₂, x₁² + x₂²). Образ f

F - эллиптический параболоид, параболоид вращения вокруг вертикальной оси, как показано на рис. 1

Очевидно, все касательные плоскости к параболоиду невертикальны, а значит, делят R³ на 2 полупространства точек, расположенных сверху и снизу от плоскости.

F обладает одним важнейшим свойством. Любая невертикальная плоскость P либо не пересекает F, либо касается в одной точке, либо проекция пересечения P и F на основную плоскость является окружностью. В последнем случае часть F под плоскостью P спроектируется внутрь круга, а то, что над плоскостью - вне его. Обратно, для любой окружности в R² существует плоскость, дающая в проекции пересечения эту окружность.

Пусть S - набор точек основной плоскости. Рассмотрим выпуклую оболочку H множества f(S). Сторону H назовем нижней стороной, если H содержется в верхнем полупространстве относительно плоскости, задаваемой этой стороной. Иначе, нижняя сторона видима наблюдателю, находящемуся очень далеко снизу, без необходимости смотреть сквозь внутренность H.

Тогда триангуляция Делоне - проекция нижних сторон H на основную плоскость.

Соответствующая функция отображает точку s в плоскость

Очевидно, P_s является касательной плоскостью к рассмотренному выше параболоиду F в точке (s, s*s). Рассмотрим также поверхность

Для точки x базовой плоскости, вертикальная высота U_s равна квадрату расстояния x до s, взятому с отрицательным знаком. Таким образом, U_s - направленный вниз параболоид, касающийся основной плоскости в точке s и находящийся под основной плоскостью. Ситуация в одномерном случае показана на рисунке 3.

Если думать о P_s, U_s и F как о функциях с основной плоскости на вертикальное направление, то, очевидно, U_s = P_s - F. Решающим рассуждением тут является то, что F не зависит от s: для точек s, s' из S и любой точки x основной плоскости, имеем P_s(x)>P_s'(x) равносильно U_s(x)>U_s'(x) тогда и только тогда, когда x дальше от s, чем от s'. Аналогично, P_s(x) = P_s'(x) тогда и только тогда, когда x равноудалена от s и s'.

Итак, пусть I - пересечение замкнутых полупространств над плоскостями P_s. Тогда диаграмма Вороного V - множество проекций сторон I на основную плоскость.

Если имеется диаграмма Вороного множества из N точек на плоскости, то выпуклая оболочка этого множества может быть найдена за линейное время.

Пусть диаграмма Вороного представлена РСДС(реберный список с двойными связями) с ориентацией обхода циклов, составляющих грани, например, против часовой стрелки. Будем перебирать ребра диаграммы до тех пор, пока не найдется луч (рис. 4). Если считать к ориентированным в направлении от бесконечности к его началу и при этом ячейка V(i) расположена справа от луча r, то точка р_i является вершиной выпуклой оболочки. Будем просматривать ребра ячейки V(i) до тех пор, пока не встретится другой луч r'. Изменив на обратную ориентацию луча r, определим следующую вершину выпуклой оболочки p_j и теперь будем просматривать ребра ячкйки V_j и т. д., пока вновь не вернемся к ячейке V(i). Ребро диаграммы просматривается лишь в том случае, если выполняется обход ребер одной из ячеек, содержащих это ребро. Так как каждое ребро принадлежит в точности двум ячейкам, то ни одно ребро не будет просмотрено более двух раз и время обработки является линейным.