Означення та властивості діаграми Вороного. Побудова діаграми Вороного

Побудова (за час ):

1. Розділити множину точок на дві приблизно рівні множини та горизонтальною прямою.

2. Рекурсивно побудувати діаграму Вороного для та .

3. Побудувати ламану , яка розділяє та .

1. Побудувати опорні відрізки до опуклих оболонок та .

2. Проводити серединний перпендикуляр до одного з опорних відрізків до перетину з якоюсь прямою з вже побудованих діаграм Вороного.

3. Дві прямі, що перетнулись, розділяють три точки. Відкидаємо спільну точку з розгляду, і продовжуємо будувати серединні перпендикуляри для двох точок, що залишилися.

4. Так будувати доти, поки ламана, не співпаде з серединним перпендикуляром до якогось іншого опорного відрізка.

4. Видалити усі ребра з діаграми верхньої множини, які лежать нижче за ламану. Аналогічно з точністю до навпаки для нижньої множини.