Page 96 - 4204

ЛЕКЦІЯ 7. ЕЛЕМЕНТИ ОБЧИСЛЮВАЛЬНОЇ ГЕОМЕТРІЇ.

но діаграму Вороного, то тріангуляцію отримують, просто

з’єднавши центри сусідніх областей діаграми. У цьому розумінні

діаграма Вороного і тріангуляція Делоне є взаємно двоїстими

(див. рис. 7.2).

Рисунок 7.2. Тріангуляція Делоне та діаграма Вороного
для заданої множини точок

Таким чином, кожна вершина многокутника є перетином се-

рединних перпендикулярів трикутника тобто є центром описа-

ного кола. Ці центри є внутрішними вершини діаграми Воро-

ного. Зовнішні вершини діаграми Вороного (ті, що лежать на

границі області) будуть утворюватись перетином серединних пе-

рпендикулярів із границею області.

95