Триангуляция Делоне

Конспект не готов.

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше?

Что такое триангуляция Делоне

Определение:

Подразбиение Делоне — такое разбиение плоскости на множество выпуклых фигур, что в окружности, описанной вокруг любой из фигур, не находится никаких точек.

Определение:

Триангуляция Делоне — триангуляция, являющаяся подразбиением Делоне.

Существование триангуляции Делоне

Откуда нам знать, что такое подразбиение вообще существует?

Спроецируем нашу плоскость на параболоид и построим трёхмерную выпуклую оболочку множества точек.

Лемма:

Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.

Доказательство:

[math]\triangleright[/math]

TODO: Янизнаюололо

[math]\triangleleft[/math]

Грани выпуклой оболочки — фигуры подразбиения Делоне. По лемме очевидно, что внутри описанных окружностей не будет лежать никаких точек. Так же очевидно, что такое подразбиение единственно. Затриангулировав фигуры подразбиения Делоне, получим триангуляцию Делоне, которая так же будет единственна (с точностью до подразбиения Делоне).