Перегляд вихідного коду сторінки Кінетична опукла оболонка

{{Мовні помилки|дата=травень 2017}}
'''Кінети́чна опу́кла оболо́нка'''&nbsp;— це спеціалізована [[кінетична структура даних]], призначена для підтримання та оновлення [[Опукла оболонка|опуклої оболонки]] множини точок, що рухаються. Ця структура дозволяє ефективно відслідковувати зміни оболонки, що виникають унаслідок постійного переміщення точок, і знаходить застосування у [[Комп'ютерний зір|комп’ютерному зорі]] й [[Робототехніка|робототехніці]] для задач навігації та візуалізації.

== 2D-випадок ==
Найбільш відомою структурою даних для двовимірної задачі кінетичної опуклої оболонки є структура Баша, {{Нп|Леонідас Гюйбас|Гюйбаса||Leonidas J. Guibas}} та Гершберга. Ця структура даних [[Кінетична структура даних#Продуктивність|релевантна, ефективна, компактна]] і [[Кінетична структура даних#Локальність|локальна]].<ref name="BGH99" />

=== Структура даних ===
[[Двоїстість (проєктивна геометрія)|Двоїста]] опукла оболонка множини точок&nbsp;— це верхній і нижній обвідний подвійний набір ліній. У такий спосіб підтримка верхніх і нижніх оболонок набору рухливих ліній еквівалентна підтримці опуклою оболонкою множини рухомих точок. Комп'ютери однаково рахують верхні і нижні оболонки, тому обчислення верхньої обвідної оболонки ліній еквівалентно обчисленню опуклої оболонки множини рухомих точок.

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

Стандартний алгоритм розгортки лінії для об'єднання верхніх оболонок розглядає всі вершини червоних і синіх верхніх оболонок, зліва направо. Останні червоні і сині точки зберігаються, як ліні розгортки. Коли точки зустрічаються, алгоритм перевіряє, якщо точка знаходиться вище або нижче лінії, тоді останніми зіткнулися точки протилежного кольору. Якщо вона вища, то точка додається в об'єднану верхню оболонку. Якщо вона іншого кольору, ніж остання додана точка (червоні і сині оболонки перетнулися), тоді точка перетину також додається в об'єднану верхню оболонку.<ref>{{Cite journal |first=John |last=Hershberger |title=Finding the upper envelope of ''n'' line segments in O(''n'' log ''n'') time |url=https://archive.org/details/sim_information-processing-letters_1989-12-21_33_4/page/169 |journal=Information Processing Letters |volume=33 |issue=4 |date=21 грудня 1989 |pages=169–174 |doi=10.1016/0020-0190(89)90136-1}}</ref>

Послідовність ребер і вершин, що випливають із цього алгоритму залежить тільки від упорядкування точок і результатів точкових порівнянь. Так, результат може бути сертифікований за наступними сертифікатами:
* Х-сертифікати (<math><_x</math>) використовуються для підтвердження порядку вершин червоних і синіх оболонок. Вони є сертифікатами для {{не перекладено|кінетичного відсортованого списку|||kinetic sorted list}} на множині вершин. Оскільки кожна точка включає в себе 2 лінії, і сертифікат включає в себе 2 точки, кожен сертифікат включає в себе 4 лінії.
* У-сертифікати (<math><_y</math>) використовуються для підтвердження, що вершина розташована вище або нижче лінії. Сертифікати з'являються для всіх порівнянь, які виникають під час роботи алгоритму.
Поки є всі ці сертифікати, етапи злиття будуть виконуватися однаково, так що в результаті верхня оболонка буде така сама, як і нижня. Кінетична структура даних для верхніх оболонок може бути створена за допомогою цих сертифікатів для підтвердження роботи статичного алгоритму верхньої оболонки. Однак ця схема не є локальною, так як одна лінія може брати участь у багатьох У-сертифікатах, якщо вона залишається на верхній або нижній частині, де зустрічаються багато точок з іншої оболонки.

Таким чином, необхідно ввести S-сертифікати (<math><_s</math>), які підтверджують, що нахил одної лінії більше або менше, ніж нахил іншої лінії.
[[Файл:Kinetic convex hull, detection of intersections.svg|thumb|540px|right|alt= Зображення сертифікатів в ряді випадків | сертифікати засвідчують структуру перетину червоних і синіх оболонок із сертифікацією перетинів (угорі ліворуч) або відсутністю перетинів (справа вгорі і внизу). Стрілки вказують, які елементи порівнюються сертифікатом.]]

Маючи такі сертифікати для всіх точок набору АВ достатньо, щоб засвідчити послідовність ребер і вершин в результаті злиття, лише за O (1) сертифікатами в рядок:<ref name="BGH99"/> 
# <math>x[ab]</math>: <math>ab<_x ab.next</math>. <math>ab.next</math> позначає вершину найближчої до <math>ab</math> з правої сторони. Цей сертифікат зберігається для всіх точок <math>ab</math>, які мають інший колір, ніж точка, <math>ab.next</math>, який слідує за ними.

# <math>yli[ab]</math>: <math>ab<_y ce(ab)</math> або <math>ab>_y ce(ab)</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, таких що <math>b</math> перетинає <math>ce(ab)</math>. <math>ce(ab)</math> позначає ребро <math>ab</math>, край іншої оболонки, який вище або нижче <math>ab</math>.
# <math>yri[ab]</math>: <math>ab<_y ce(ab)</math> або <math>ab>_y ce(ab)</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, таких що <math>a</math> перетинає <math>ce(ab)</math>.
# <math>yt[ab]</math>: <math>ce(ab)<_yab</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, для яких виконується <math>a<_sce(ab)<_s b</math> та <math>ce(ab)<_yab</math>.
# <math>srt[ab]</math>: <math>a<_sce(ab)</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, для яких виконується <math>a<_sce(ab)<_s b</math> та <math>ce(ab)<_yab</math>.
# <math>srt[ab]</math>: <math>ce(ab)<_s b</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, для яких виконується <math>a<_sce(ab)<_s b</math> та <math>ce(ab)<_yab</math>.
# <math>sl[ab]</math>: <math>b<_sce(ab)</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, для яких виконується <math>b<_sce(ab)</math> та <math>ab<_yce(ab)</math>.
# <math>sr[ab]</math>: <math>ce(ab)<_sa</math>. Цей сертифікат зберігається для всіх точок <math>ab</math>, для яких виконується <math>ce(ab)<_sa</math> та <math>ab<_yce(ab)</math>.

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

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

=== Продуктивність ===
Ця структура даних [[Кінетична структура даних#Локальність|локальна]], [[компактність|компактна]] й [[ефективність|ефективна]]. Це пов'язано з логарифмічною глибиною злиття, які використовуються для сертифікації верхньої оболонки.<ref name="BGH99" />
* '''Локальність:''' Кожний рядок бере участь у більшості з 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'').
* '''Ефективність:''' Максимальна кількість подій, оброблених цим алгоритмом на [[Кінетична структура даних#Типи траєкторій|алгебраїчній]] або псевдо-алгебраїчній траєкторії є квадратичною, <math>O(n^{2+\epsilon})</math> для всіх <math>\epsilon>0</math>.<ref name="ASS96">{{Cite journal |first1=Pankaj K. |last1=Agarwal |first2=Otfried |last2=Schwarzkopf |first3=Micha |last3=Sharir |title=The overlay of lower envelopes and its applications |journal=Discrete and Computational Geometry |volume=15 |issue=1 |pages=1–13 |date=January 1996 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5488 |doi=10.1007/BF02716576 |accessdate=28 травня 2017 |archive-date=6 березня 2016 |archive-url=https://web.archive.org/web/20160306083112/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5488 }}</ref><ref name="Sha94">{{cite journal |first=Micha |last=Sharir |title=Almost tight upper bounds for lower envelopes in higher dimensions. Discrete and Computational Geometry |volume=12 |issue=1 |pages=327–345 |year=1994 |doi=10.1007/BF02574384 }}
</ref> Опуклі оболонки лінійно рухомих точок можуть бути побудовані в <math>\Omega(n^2)</math> раз.<ref name="AGHV01">{{Cite journal|first1=Pankaj K.|last1=Agarwal|first2=Leonidas J.|last2=Guibas|first3=John|last3=Hershberger|first4=Eric|last4=Veach|title=Maintaining the extent of a moving point set|journal=Discrete and Computational Geometry|volume=26|issue=3|pages=353–374|date=January 2001|doi=10.1007/s00454-001-0019-x}}<!--The author's web site at http://www.cs.duke.edu/~pankaj/papers/ links to what is claimed to be this paper, but it looks like the 1997 version; compare the third sentence of the abstract. Also, that link is to an 11-page paper; the published one is 22 pages. That seems like too large a difference for formatting.--></ref> Таким чином, ця структура даних є ефективною.

== Вищі розміри ==
Знаходження[[ефективність| ефектівної]] кінетичної структури даних для підтримання опуклої оболонки рухомих точок у вимірах вище 2 є відкритою проблемою.<ref name="BGH99">{{cite journal |first1=Julien |last1=Basch |first2=Leonidas J. |last2=Guibas |first3=John |last3=Hershberger |title=Data structures for mobile data |journal=J. Algorithms |volume=31 |issue=1 |pages=1&ndash;28 |date=April 1999 |url=http://graphics.stanford.edu/courses/cs268-11-spring/notes/kinetic.pdf |doi=10.1006/jagm.1998.0988 |accessdate=28 травня 2017 |archive-date=5 березня 2016 |archive-url=https://web.archive.org/web/20160305065514/http://graphics.stanford.edu/courses/cs268-11-spring/notes/kinetic.pdf }}</ref>

== Пов'язані проблеми ==
Кінетична опукла оболонка може бути використана для вирішення наступних супутніх проблем:<ref name="AGHV97">{{Cite conference |first1=Pankaj K. |last1=Agarwal |first2=Leonidas J. |last2=Guibas |first3=John |last3=Hershberger |first4=Eric |last4=Veach |title=Maintaining the extent of a moving point set |conference=5th Workshop on Algorithms and Data Structures (WADS '97) |conference-url=http://www.tuns.ca/~wads/program.html |book-title=Lecture Notes in Computer Science Volume 1272 |pages=31-44 |date=August 1997 |url=https://graphics.stanford.edu/papers/extent/ |doi=10.1007/3-540-63307-3_46 |accessdate=28 травня 2017 |archive-date=29 серпня 2017 |archive-url=https://web.archive.org/web/20170829061229/https://graphics.stanford.edu/papers/extent/ }}<!--Another copy at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.8510--></ref>

* {{не перекладено|Кінетичний діаметр|||Kinetic diameter (data)}}
* {{не перекладено|Кінетична ширина|||Kinetic width}}
* {{не перекладено|Кінетичний мінімальний ящик|||Kinetic minimum box}}
* {{не перекладено|Кінетичний маленький вшитий диск|||Kinetic smallest enclosing disk}}

== Посилання ==
{{Reflist}}

{{Ізольована стаття|кільце2}}
[[Категорія:Структури даних]]
[[Категорія:Алгоритми обчислення опуклої оболонки]]