Задача динамічної підтримки опуклої оболонки

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

Формальна постановка задачі

Задані порожня множина S і послідовність із N точок (р₁, р₂, ..., р_N ), кожна з яких або додається до множини S, або вилучається з неї. Необхідно підтримувати опуклу оболонку множини S. Використовується той факт, що границя опуклої оболонки є об'єднанням двох (опуклих) монотонних ламаних ліній (ланцюгів), які обмежують оболонку зверху і знизу і відповідно до цього називаються В-оболонкою і Н-оболонкою множини точок. Розглянемо побудову В-оболонки.

Алгоритм

Відповідна структура даних організована наступним чином. Її основою є збалансоване за висотою двійкове дерево пошуку Т, листки якого використовуються для збереження точок поточної множини. Процедура пошуку буде проводитися відповідно до значення абсциси точок, тобто проходження листків дерева зліва направо дає множину точок, впорядковану за x-координатою. Зазначимо, що послідовність точок В-оболонки (її вершин) також впорядкована за зростанням абсциси, і, тому вона є підпослідовністю глобальної послідовності точок, яка зберігається в листках дерева. Упорядковуємо S за x-координатою. Нехай v — вузол дерева Т. Позначимо через ЛСИН[v] і ПСИН[v] його лівого і правого нащадків відповідно. Побудуємо В-оболонку точок, які зберігаються в листках піддерева з коренем у вузлі v. Позначимо через U(v) В-оболонку множини точок, які зберігаються в листках піддерева з коренем v. Виходячи із принципу індукції, припустимо, що вже існують U(ЛСИН[v]) і U(ПСИН[v]). Далі (мал. 2) визначаються дві опорні точки р₁ і р₂ єдиного спільного опорного відрізку для двох оболонок. Тут використовується функція З'ЄДНАТИ(U₁, U₂), яка дозволяє знайти опорний відрізок для двох В-оболонок U₁, U₂. Функція З'ЄДНАТИ дозволяє ефективно розчіпляти U₁ на два ланцюги, які складають впорядковану пару (U₁₁, U₁₂), і аналогично U₂- на пару ланцюгів (U₂₁, U₂₂). При цьому виконується така умова: опорна точка р₁ ∈ U₁ входить до складу U₁₁, а точка р₂ ∈ U₂ — до складу U₂₂ (тобто в обох випадках опорна точка належить «зовнішньому» підланцюгу). На цьому етапі, зчепивши U₁₁ і U₂₂, одержуємо шукану В-оболонку U₁ ∪ U₂. Природно, щоб кожен вузол v дерева Т вказував на зчеплену чергу, яка представляє ту частину U(v), яка не належить U(БАТЬКО[v]).
Обернена операція: маючи U(v), одержати U(ЛСИН[v]) і U(ПСИН[v]).
Знаючи ребро [р₁, р₂], яке з'єднує опорні точки (одне ціле число J[v], яке вказує на положення точки р₁ у ланцюзі вершин U(v)), можна розчепити U(v) на ланцюги U₁₁ і U₂₂, які в свою чергу можуть бути зчеплені з ланцюгами, що зберігаються в ЛСИН[v] і ПСИН[v] відповідно. Структура даних Т доповнюється такими атрибутами, які пов'язуються з кожним вузлом v дерева:

1. Вказівником на зчеплену чергу Q[v], яка містить частину U(v), що не входить до U(БАТЬКО[v]) (якщо v є коренем, то Q[v]=U(v)).
2. Цілим числом J[v], яке вказує на положення (індекс) лівої опорної точки в U(v)

Функція З'ЄДНАТИ(U₁, U₂):

1. Знайти р₁ і р₂.
2. Розчепити U₁ на U₁₁ та U₁₂.
3. Розчепити U₂ на U₂₁ та U₂₂.
4. Зчепити U₁₁ з U₂₂ ⇔ CH(S₁ ∪ S₂): U₁₁*U₂₂

Структура даних використовує пам'ять об'ємом О(N).
Враховуючи, що операції розчеплення і зчеплення зчеплених черг є стандартними, наша увага буде зосереджена на операції, що виконується функцією З'ЄДНАТИ, для якої був запропонований наступний розв'язок:
Лема 1 З'єднання двох розділених опуклих ланцюгів, які містять в сумі N точок, може бути виконане за О(logN) кроків.
Доведення. Нехай дано дві В-оболонки U₁, U₂ і дві вершини q₁ ∈ U₁, q₂∈U₂. Кожна із цих двох вершин може бути класифікована відносно відрізка [q₁,q₂] як опукла, опорна або ввігнута. Залежно від класифікації можливі 9 випадків, схематично зображених на малюнку 3(а). Усі випадки зрозумілі за винятком випадку (q₁,q₂) = (ввігнута, ввігнута), який детальніше представлений на малюнку 3 (б). Нехай пряма l₁ проходить через q₁ і її правого сусіда на U₁. Аналогічно пряма l₂ проходить через q₂ і її лівого сусіда на U₂. Позначимо через р точку перетину прямих l₁ і l₂. U₁ і U₂ розділимі вертикаллю l.

1. Припустимо, що точка р знаходиться праворуч від прямої l. р₁ може належати лише заштрихованій області і u(y) < v(y) ⇒ довільна вершина q" ∈ U_2прав. відносно q₂, є ввігнутою відносно відрізка [q',q"], де q' — довільна вершина U₁ і U_2прав. відносно q₂ не розглядається. Що стосується ланцюга ліворуч від вершини q₁, то для нього не можна це стверджувати.
   
2. Якщо точка перетину р знаходиться ліворуч від прямої l, то ланцюг ліворуч від вершини q₁ можна не розглядати.

Посилання

• Підтримка динамічної опуклої оболонки - основні алгоритми обчислювальної геометрії
• Overmars, M. H.; van Leeuwen, J. (1981), Maintenance of configurations in the plane, Journal of Computer and System Sciences, 23 (2): 166—204, doi:10.1016/0022-0000(81)90012-X.
• Jacob Rico, Dynamic Planar Convex Hull [Архівовано 4 червня 2011 у Wayback Machine.] (2002), a BRICS [Архівовано 22 квітня 2011 у Wayback Machine.] dissertation