Эти две конструкции двойственны. То есть из одной можно просто получить другую. Вообще говоря, диаграмма Вороного уникальна для данного набора точек, а триангуляция Делоне - не всегда. Однако, если есть несколько триангуляций, то они эквивалентны в том смысле, что их минимальные углы равны. Так что можно говорить об однозначном соответствии между диаграммой Вороного и триангуляциями Делоне. Посмотрим, например, как из диаграммы получается триангуляция. Если две точки pi и pj из P имеют общее ребро диаграммы(их ячейки смежные), провести дугу между pi и pj. Получится граф Делоне, обозначенный на первом рисунке буквой G Затем натягиваем дуги, превращая в отрезки. Таким образом, триангуляция получается соединением всех смежных точек P отрезками. Единственная проблема: четыре или более точек в графе Делоне могут лежать на одной окружности. Такие точки образуют выпуклые полигоны, которые триангулируются добавлением произвольных непересекающихся диагоналей. Тогда триангуляция будет окончательной. Можно сказать, что триангуляция Делоне получается из графа Делоне добавлением 0 или более ребер.  8  Комментарии к статье  8 8  Обсудить в чате