Попередня Змiст Наступна

5.5. ПОБУДОВА ДІАГРАМИ ВОРОНОГО.

Діаграма Вороного - планарний граф. Результат - РСПЗ.
Теорема 6.1 Для побудови діаграми Вороного множини з N точок необхідно W(NlogN) операцій в гіршому випадку.
Вершини Діаграми Вороного в E1.
Наслідок. CОРТУВАННЯ N ДІАГРАМИ ВОРОНОГО
Діаграма Вороного( схема "розподіляй та володарюй")

Крок 1. Розділити множину S на дві приблизно рівні підмножини S1 та S2.
Крок 2. Рекурсивно побудувати Vor(S1) та Vor(S2).
Крок 3. Об'єднати Vor(S1) та Vor(S2) і таким чином отримати Vor(S).
Означення 5.6 Нехай для заданого розбиття {S1, S2} множини S s (S1, S2) означає множину ребер діаграми Вороного, спільних для пар многокутників V(i) та V(j) діаграми Vor(S), де pi S1 та pj S2.
Теорема 6.2 Сукупність s(S1, S2) є множиною ребер деякого підграфа діаграми Vor(S) і має такі властивості:
  1. s(S1, S2) складається із циклів та ланцюгів, що не мають спільних ребер. Якщо деякий ланцюг містить єдине ребро, то це ребро є прямою лінією; інакше два крайні ребра ланцюга є промінями.
  2. Якщо множини S1 та S2 є лінійно роздільними, то s(S1, S2) складається з єдиного монотонного ланцюга.
Доведення.
  1. Якщо уявити, що кожний із многокутників {V(i): pi S1} розфарбований у червоний колір, а кожний із многокутників {V(j): pj S2} - у зелений, то Vor(S) перетвориться у двоколірну карту. Відомо, що границі між многокутниками різних кольорів представляють цикли та ланцюги, які не мають спільних ребер. Кожна компонента множини s(S1, S2) розбиває площину на дві частини. Таким чином ланцюг містить єдине ребро, яке представляє собою пряму лінію, або його перше та останнє ребра є промені.
  2. Якщо множини S1 і S2 лінійно роздільні, то єдиний ланцюг, який міститься у s(S1, S2), позначатимемо s. Якщо розділяюча пряма m вертикальна, то s розділяє площину на ліву pL та праву pR частини.
Мал. 5.17(а).Монотонність x(p3) < x(p1) < x(p2), (p3, p2) S1, p1 S2 ==> v1 не існує.
Мал. 5.17(б). Монотонність: x(p1) < x(p2) < x(p3), (p3, p1)S1, p2 S2==> v1 протиріччя.
Теорема 5.13 Якщо множини S1 і S2 лінійно розділені вертикальною прямою і при цьому S1 міститься ліворуч від S2, то діаграма Вороного Vor(S) являє собою об'єднання Vor(S1) pL і Vor(S2) pR.

procedure ДІАГРАМА ВОРОНОГО
Крок 1. Розділити множину S на дві приблизно рівні підмножини S1 та S2, використавши для цього медіану, за x-координатою.
Крок 2. Рекурсивно побудувати Vor(S1) та Vor(S2).
Крок 3'. Побудувати ламану s, що розділяє S1 та S2.
Крок 3". Вилучити усі ребра діаграми Vor(S2), розташовані зліва від s, та всі ребра Vor(S1), розташовані справа від s. Отримаємо Vor(S) - діаграму Вороного для всієї множини.

Попередня Змiст Наступна