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

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

Диаграмма Вороного конечного множества точек на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества, чем к любому другому элементу множества (Рисунок. 5, a) [5]. Совокупность многоугольников Вороного образует разбиение плоскости, представляющее векторную сеть.

Одним из главных свойств диаграммы Вороного является её двойственность триангуляции Делоне. А именно, соединив отрезками те исходные точки, чьи многоугольники Вороного соприкасаются хотя бы углами, мы получим триангуляцию Делоне (Рисунок. 5, б).

Диаграмма Вороного имеет много областей применения.

В качестве примера рассмотрим некоторые из них:

• · Нахождение ближайшей точки для каждой. Отметим простой факт: если для точки ближайшей является точка, то эта точка имеет «своё» ребро в ячейке. Отсюда следует, что, чтобы найти для каждой точки ближайшую к ней, достаточно просмотреть рёбра её ячейки Вороного. Однако каждое ребро принадлежит ровно двум ячейкам, поэтому будет просмотрено ровно два раза, и вследствие линейности числа рёбер мы получаем решение данной задачи за .
• · Нахождение выпуклой оболочки. Вспомним, что вершина принадлежит выпуклой оболочке тогда и только тогда, когда её ячейка Вороного бесконечна. Тогда найдём в диаграмме Вороного любое бесконечное ребро, и начнём двигаться в каком-либо фиксированном направлении (например, против часовой стрелки) по ячейке, содержащей это ребро, пока не дойдём до следующего бесконечного ребра. Тогда перейдём через это ребро в соседнюю ячейку и продолжим обход. В результате все просмотренные рёбра (кроме бесконечных) будут являться сторонами искомой выпуклой оболочки. Очевидно, время работы алгоритма .

· Нахождение Евклидова минимального остовного дерева. Требуется найти минимальное остовное дерево с вершинами в данных точках, соединяющее все эти точки. Если применять стандартные методы теории графов, то, т.к. граф в данном случае имеет рёбер, даже оптимальный алгоритм будет иметь не меньшую асимптотику. Рассмотрим граф, двойственный диаграмме Вороного, т. е. триангуляцию Делоне. Можно показать, что нахождение Евклидова минимального остова эквивалентно построению остова триангуляции Делоне. Действительно, в алгоритме Прима каждый раз ищется кратчайшее ребро между двумя множествами точек; если мы зафиксируем точку одного множества, то ближайшая к ней точка имеет ребро в ячейке Вороного, поэтому в триангуляции Делоне будет присутствовать ребро к ближайшей точке, что и требовалось доказать.

Триангуляция является планарным графом, т. е. имеет линейное число рёбер, поэтому к ней можно применить алгоритм Крускала и получить алгоритм с временем работы .

· Нахождение наибольшей пустой окружности. Требуется найти окружность наибольшего радиуса, не содержащую внутри никакую из точек (центр окружности должен лежать внутри выпуклой оболочки точек). Заметим, что, т.к. функция наибольшего радиуса окружности в данной точке является строго монотонной внутри каждой ячейки Вороного, то она достигает своего максимума в одной из вершин диаграммы Вороного, либо в точке пересечения рёбер диаграммы и выпуклой оболочки (а число таких точек не более чем в два раза больше числа рёбер диаграммы). Таким образом, остаётся только перебрать указанные точки и для каждой найти ближайшую, т. е. решение за .

Рисунок 5. Диаграммы Вороного: а) — пример диаграммы; б) — двойственная диаграмме триангуляция Делоне.