Кінетична опукла оболонка

Кінети́чна опу́кла оболо́нка — це спеціалізована кінетична структура даних, призначена для підтримки та оновлення опуклої оболонки множини точок, що рухаються. Ця структура дозволяє ефективно відслідковувати зміни оболонки, що виникають внаслідок постійного переміщення точок, і знаходить застосування у комп’ютерному зорі та робототехніці для задач навігації та візуалізації.

2D-випадок

Найбільш відомою структурою даних для 2-вимірної задачі кінетичної опуклої оболонки є структура Баша, Гюйбаса та Гершберга. Ця структура даних релевантна, ефективна, компактна і локальна.

Структура даних

Двоїста опукла оболонка множини точок — це верхній і нижній обвідний подвійний набір ліній. Таким чином, підтримка верхніх і нижніх оболонок набору рухливих ліній еквівалентна підтримці опуклою оболонкою множини рухомих точок. Комп'ютери однаково рахують верхні і нижні оболонки, тому обчислення верхньої обвідної оболонки ліній еквівалентно обчисленню опуклої оболонки множини рухомих точок. Верхня оболонка, що огинає набір статичних рядків, може бути обчислена за допомогою алгоритму розділяй і володарюй, який розбиває рядки на дві групи однакового розміру, викликає себе рекурсивно для двох наборів, щоб знайти їх верхні оболонки, а потім зливає дві оболонки в одну. Крок злиття виконується з використанням алгоритму замітання прямою. Функція розглядає перший набір синіх точок і другий набір червоних точок.

Стандартний алгоритм розгортки лінії для об'єднання верхніх оболонок розглядає всі вершини червоних і синіх верхніх оболонок, зліва направо. Останні червоні і сині точки зберігаються, як ліні розгортки. Коли точки зустрічаються, алгоритм перевіряє, якщо точка знаходиться вище або нижче лінії, тоді останніми зіткнулися точки протилежного кольору. Якщо вона вища, то точка додається в об'єднану верхню оболонку. Якщо вона іншого кольору, ніж остання додана точка (червоні і сині оболонки перетнулися), тоді точка перетину також додається в об'єднану верхню оболонку.

Послідовність ребер і вершин, що випливають з цього алгоритму залежить тільки від упорядкування точок і результатів точкових порівнянь. Таким чином, результат може бути сертифікований з наступними сертифікатами:

• Х-сертифікати ($<_{x}$) використовуються для підтвердження порядку вершин червоних і синіх оболонок. Вони є сертифікатами для кінетичного відсортованого списку на множині вершин. Так як кожна точка включає в себе 2 лінії, і сертифікат включає в себе 2 точки, кожен сертифікат включає в себе 4 лінії.
• У-сертифікати ($<_{y}$) використовуються для підтвердження, що вершина знаходиться вище або нижче лінії. Сертифікати з'являються для всіх порівнянь, які виникають під час роботи алгоритму.

Поки є всі ці сертифікати, етапи злиття будуть виконуватися однаково, так що в результаті верхня оболонка буде така ж сама, як і нижня. Кінетична структура даних для верхніх оболонок може бути створена за допомогою цих сертифікатів для підтвердження роботи статичного алгоритму верхньої оболонки. Однак ця схема не є локальною, так як одна лінія може брати участь у багатьох у-сертифікатах, якщо вона залишається на верхній або нижній частині, де зустрічаються багато точок з іншої оболонки.

Таким чином, необхідно ввести S-сертифікати ($<_{s}$), які підтверджують, що нахил одної лінії більше або менше, ніж нахил іншої лінії.

сертифікати засвідчують структуру перетину червоних і синіх оболонок із сертифікацією перетинів (угорі ліворуч) або відсутністю перетинів (справа вгорі і внизу). Стрілки вказують, які елементи порівнюються сертифікатом.

Маючи такі сертифікати для всіх точок набору АВ достатньо, щоб засвідчити послідовність ребер і вершин в результаті злиття, лише за O (1) сертифікатами в рядок:

1. $x[ab]$: $ab<_{x}ab.next$. $ab.next$ позначає вершину найближчої до $ab$ з правої сторони. Цей сертифікат зберігається для всіх точок $ab$, які мають інший колір, ніж точка, $ab.next$, який слідує за ними.

1. $yli[ab]$: $ab<_{y}ce(ab)$ або $ab>_{y}ce(ab)$. Цей сертифікат зберігається для всіх точок $ab$, таких що $b$ перетинає $ce(ab)$. $ce(ab)$ позначає ребро $ab$, край іншої оболонки, який вище або нижче $ab$.
2. $yri[ab]$: $ab<_{y}ce(ab)$ або $ab>_{y}ce(ab)$. Цей сертифікат зберігається для всіх точок $ab$, таких що $a$ перетинає $ce(ab)$.
3. $yt[ab]$: $ce(ab)<_{y}ab$. Цей сертифікат зберігається для всіх точок $ab$, для яких виконується $a<_{s}ce(ab)<_{s}b$ та $ce(ab)<_{y}ab$.
4. $srt[ab]$: $a<_{s}ce(ab)$. Цей сертифікат зберігається для всіх точок $ab$, для яких виконується $a<_{s}ce(ab)<_{s}b$ та $ce(ab)<_{y}ab$.
5. $srt[ab]$: $ce(ab)<_{s}b$. Цей сертифікат зберігається для всіх точок $ab$, для яких виконується $a<_{s}ce(ab)<_{s}b$ та $ce(ab)<_{y}ab$.
6. $sl[ab]$: $b<_{s}ce(ab)$. Цей сертифікат зберігається для всіх точок $ab$, для яких виконується $b<_{s}ce(ab)$ та $ab<_{y}ce(ab)$.
7. $sr[ab]$: $ce(ab)<_{s}a$. Цей сертифікат зберігається для всіх точок $ab$, для яких виконується $ce(ab)<_{s}a$ та $ab<_{y}ce(ab)$.

Перший сертифікат, $x[ab]$, засвідчує х-упорядкування точок в червоних і синіх оболонках. Другі і треті сертифікати, $yli[ab]$ та $yri[ab]$, засвідчують перетин червоних і синіх оболонок. Решта 5 сертифікатів, $yt[ab]$, $srt[ab]$, $srt[ab]$, $sl[ab]$, та $sr[ab]$ розміщюють ребра, яких не має в верхніх оболонках в послідовності схилів ребер. Якщо нахил на початку або в кінці послідовності, $sl$ або $sr$ засвідчать це. Якщо він знаходиться в середині послідовності $slt$, та $srt$ засвідчити це, і $yt$ засвідчує, що точка перетину двох ліній, знаходиться над ребром. Цих одного або трьох сертифікатів досить, щоб довести, що всі ребра знаходяться вище опорної лінії. На відміну від попередньої схеми всі лінії лише беруть участь в постійній кількості сертифікатів. Всякий раз, коли з цих сертифікатів не вийде нової лінії, об'єднана оболонка і сертифікати можуть бути оновлені за O (1) .

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

Продуктивність

Ця структура даних локальна, компактна і ефективна. Це пов'язано з логарифмічною глибиною злиття, які використовуються для сертифікації верхньої оболонки.

• Локальність: Кожний рядок бере участь в більшості з O (log n") сертифікатів. Це тому, що кожна лінія бере участь в постійній кількості сертифікатів в кожному злитті, і кожен рядок знаходиться в O (log n) час злиття.
• Компактність: Максимальна кількість сертифікатів, які використовуються в цій структурі даних дорівнює О (n log n). Це відбувається тому, що кожне злиття включає в себе ряд лінійних сертифікатів по числу злитих ліній. Верхня оболонка із n ліній вимагає сертифікатів для злиття верхніх двох підмножин з n / 2 рядками і сертифікатами для злиття оболонок. Таким чином, кількість сертифікатів, C (n), що створюють верхню оболонку з n ліній задовольняє співвідношенню C (n) = 2C (n / 2) + О (n), де С (1) = O (1). Основна теорема, де С (n) = O (n log n).
• Ефективність: Максимальна кількість подій, оброблених цим алгоритмом на алгебраїчній або псевдо-алгебраїчній траєкторії є квадратичною, $O(n^{2+\epsilon })$ для всіх $\epsilon >0$. Опуклі оболонки лінійно рухомих точок можуть бути побудовані в $\Omega (n^{2})$ раз. Таким чином, ця структура даних є ефективною.

Вищі розміри

Знаходження ефектівної кінетичної структури даних для підтримки опуклої оболонки рухомих точок в вимірах вище 2 є відкритою проблемою.

Пов'язані проблеми

Кінетична опукла оболонка може бути використана для вирішення наступних супутніх проблем:

Див. також

• Кінетичний діаметр
• Кінетична ширина
• Кінетичний мінімальний ящик
• Кінетичний маленький вшитий диск