24. Свойства диаграммы Вороного. Двойственный граф есть триангуляция.

Триангуляция точечного множества – разбиение выпуклой оболочки на треугольники, вершинами которых являются все точки исходного множества, и только они.

Граф, двойственный диаграмме Вороного, есть триангуляция.

Граф называется двойственным диаграмме Вороного, если его ребрами являются все отрезки, соединяющие точки исходного множества, лежащие в смежных областях близости.

Утверждение: 1)каждая точка плоскости принадлежит хотя бы одному треугольнику, и 2)эти треугольники не пересекаются

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

2) Возьмем два любых треугольника и построим для них описанные окружности. Если окружности не пересекаются, то и треугольники не пересекаются. Иначе: по второму свойству диаграммы Вороного на дуге, принадлежащей другому кругу, не может быть точек множества и соответственно вершин треугольника. Следовательно, треугольники не имеют общих точек.

1)Предположим, что точка плоскости А не принадлежит ни одному из треугольников. Тогда существует E – окрестность точки А, точки которой не принадлежат треугольникам.

Возьмем точку Т, принадлежащую какому-либо треугольнику, соединим точки А и Т отрезком, который не будет проходить ни через одну точку исходного множества (при "прохождении" возьмем точку А` из E – окрестности точки А). Этот отрезок обязательно пересечет ребра треугольников (хотя бы одно), из этих пересечений найдем ближайшее к А`. P0 P1 – точки исходного множества из смежных областей. P2 – третья вершина треугольника с ребром P0P1. Если P2 лежит относительно P0P1 ближе к А`, значит точка Q – не последнее пересечение. Если P2 лежит относительно P0P1 ближе к Т, то:

Пусть v – вершина диаграммы Вороного. Тогда ребро e – конечно, иначе P0P1 – ребро выпуклой оболочки, то есть А` не лежит внутри выпуклой оболочки, что противоречит начальным условиям. Следовательно, существует треугольник, которому принадлежит точка А.

Свойство диаграммы Делоне: внутри окружностей, описанных вокруг любого треугольника, нет других исходных точек.

Триангуляция из Диаграммы Вороного строится за O(n).