5.6. ПОБУДОВА РОЗДІЛЯЮЧОГО ЛАНЦЮГА.
Кожний промінь ланцюга s перпендикулярний опорному відрізку до CH(S1) та CH(S2) і ділить його навпіл. Оскільки S1 та S2 за припущенням лінійно роздільні, то існує рівно два опорних відрізки до CH(S1) та CH(S2).
Знайшовши промінь ланцюга s,
послідовно будуємо ребра ланцюга до досягнення другого променя (мал. 5.18).
Мал. 5.18. Визначення променів ланцюгf s
Приклад 4. Будуємо множину ребер
розділяючого ланцюга між вхідним та вихідним променями (мал. 5.19).
Верхній промінь s, перпендикулярний до опорного відрізка 15
і ділить його навпіл. Уявімо точку z, яка, рухаючись по верхньому
променю, перетне ребро діаграми Vor(S2). Отже
точка z переходить із області близькості точки 5
в область близькості точки 6, тобто стає ближчою до 6 ніж до 5.
Тому промінь e2 буде перпендикулярним відрізку 16.
Рухаючись по променю e2,
точка z перетне ребро Vor(S1),
тобто вона перейде із області близькості точки 1 у область близькості точки 2,
тому e3 стає перпендикулярним 26 і т.д.
( e4 ^ 27, e5 ^ 7, e6 ^ 48 ).
Мал. 5.19. Побудова розділяючого ланцюга.
Для визначення точок перетину ланцюга s
з V(i) у Vor(S1)
необхідно переглядати ребра за годинниковою стрілкою.
Для s з V(j) у
Vor(S2) - навпаки (мал. 5.20).
Мал. 5.20. Перетин ланцюга s з V(i) у Vor(S1).
Позначення: I(e, e') - перетин
відрізків e і e',
а I(e, e') = L означає,
що e і e' не перетинаються;
t1 і t2 - два опорних
відрізки, при цьому t1 = [p,q].
Розглянемо реалізацію кроку 3' процедури ДІАГРАМА ВОРОНОГО.
- begin pL : = p; pR : = q; e : = e*; v : = v*;
eL : = перше ребро (відкритої) границі V(pL);
eR : = перше ребро (відкритої) границі V(pR);
- repeat
- while(I(e, eL) = L ) do eL : = Н1[еL] (* подивитись границю V(pL)*);
while(I(e, eR) = L ) do eR : = Н2[еR] (* подивитись границю V(pR)*);
- if(v ближче до I(e, eL), ніж до I(e, eR)) then
- begin v: = I(e, eL);
- pL : = точка S, яка міститься по іншу сторону від eL (сусід (pL));
- e: = пряма, перпендикулярна [pL, pR] і, яка ділить його навпіл;
- eL : = обернене до eL (*нове eL є ребром V(pL)*);
end
- else begin v: = I(e, eR);
- pR : = точка S, яка міститься по іншу сторону від eR (сусід (pR));
- e: = пряма, перпендикулярна [pL, pR] і, яка ділить його навпіл;
- eR : = обернене до eR
end
- until ([pL, pR] = t2)
end
Після ініціалізації (рядок 1) відбувається рух по ланцюгу s (2-14).
Теорема 5.14 Діаграму Вороного на множині
із N точок площини можна побудувати з оптимальним часом Q(NlogN).
