Випукла оболочка

Реферат на тему:

Опукла оболонка.

Означення. Афінна геометрія складається з множини скалярів S (дійсних чисел), множини точок P та множини вільних векторів V (або просто векторів). Точки використовуються для задання положення, а вектори — для задання напрямку та величин, хоча вони і не мають фіксованого положення у просторі.

Операції афінної геометрії:

1. добуток скаляра на вектор: S * V xF0AExF020V;

2. додавання векторів: V + V xF0AExF020V;

3. віднімання точок: P — P xF0AExF020V;

4. додавання точки та вектора: P + V xF0AExF020P;

додавання векторів віднімання точок додавання точок та вектора Різницею двох точок p та q буде вектор, який направлево з q до p.

Кількість операцій можна розширити. Наприклад, різницю векторів можна визначити як u — v = u + (-1) * v, а ділення вектора на скаляр як v / a = (1 / a) * v. Але не можна додавати дві точки або множити точку на скаляр.

Означення. Нехай в Ed задано k різних точок p1, p2, …, pk. Множина точок p таких що.

p = a1p1 + a2p2 + … + akpk (ai xF0CExF020R, a1 + a2 + …+ ak = 1).

називається афінною множиною, породженою точками p1, p2, …, pk, а p називається афінною комбінацією точок p1, p2, …, pk.

Афінна комбінація є частковим випадком лінійної комбінації (вводиться додаткова умова a1 + a2 + …+ ak = 1). При k = 2 афінна множина — це пряма, що проходить через дві точки p1 та p2.

Приклад. Нехай дано дві точки p1, p2 та число а. Позначимо через Aff (p0, p1, a) комбінацію (1 — a) * p1 + a * p2 = p1 + a * (p2 — p1). Ліва частина рівності містить недопустиму операцію (додавання точок), але еквівалентний їй алгебраїчний вираз правої частини є допустимим. Якщо p1 xF0B9xF020p2, то Aff (p0, p1, a) лежить на прямій p1p2. Коли, а пробігає всі дійсні значення, то вираз Aff (p0, p1, a) пробігає всі точки прямої p1p2. При a xF0CExF020[0; 1] значення Aff (p0, p1, a) пробігає всі точки відрізку [p; q].

Для представлення векторів та точок в афінному просторі використовуються гомогенні координати. При роботі з d вимірним афінним простором координати будемо представляти (d + 1) — кортежами дійсних чисел. Перший елемент кортежа дорівнює 1 для точки і 0 для вектора. Інші d елементів кортежа відповідають безпосередньо координатам.

P (1; 1; 3), Q (1; 4; 1), u (0; 1; 2).

P — Q = (1−1; 1−4; 3−1) = (0; -3; 2).

Означення. Три точки p, q, r на площині мають додатню орієнтацію, якщо вони утворюють трикутник, орієнтований проти годинникової стрілки та від'ємну орієнтацію, якщо обхід трикутника pqr відбувається за годинниковою стрілкою. Три точки p, q, r мають нульову орієнтацію, якщо вони лежать на одній прямій.

додатня нульова від'ємна Орієнтація визначається знаком детермінанта, визначеного координатами трьох точок в гомогенних координатах:

Означення. Нехай в просторі Ed задана підмножина L. Афінною оболонкою aff (L) множини L називається найменша афінна множина, яка містить L.

Афінною оболонкою відрізка є пряма, афінною оболонкою плоского многокутника є площина.

Означення. Нехай в Ed задано k різних точок p1, p2, …, pk. Множина точок p таких що.

p = a1p1 + a2p2 + … + akpk (ai xF0CExF020R, ai xF0B3xF0200, a1 + a2 + …+ ak = 1).

називається опуклою множиною, породженою точками p1, p2, …, pk, а p називається опуклою комбінацією точок p1, p2, …, pk.

Опукла комбінація є звуженням афінної комбінації. При k = 2 опуклою множиною є відрізок, який сполучає задані точки.

Означення. Нехай в просторі Ed задана підмножина L. Опуклою оболонкою conv (L) множини L називається найменша опукла множина, яка містить L.

Означення. Поліедральною множиною в називається перетин скінченної множини замкнених півпросторів (півпростір — це частина Ed, розташована по одну сторону від деякої гіперплощини).

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

Теорема. Опукла оболонка скінченної множини точок в є опуклим політопом. Кожний опуклий політоп є опуклою оболонкою деякої скінченної множини точок.

Опуклий політоп задається описом його границі, яка складається з граней. Кожна грань опуклого політопа є опуклою множиною (політопом низької розмірності). Якщо політом має вимірність d, то його d — 1 грані називаються гіпергранями, d — 2 грані - підгранями, 1 — грані - ребрами, 0 — грані - вершинами. Для 3 політопа гіпергранями є плоскі многокутники, а підграні та ребра співпадають. В цій термінології порожня множина трактується як (-1) грань.

Означення. d політоп називається d симплексом, якщо він є опуклою оболонкою (d + 1) афінно незалежних точок. Кожна підмножина з цих d вершин є симплексом і є гранню. Кожна k грань містить 2k+1 граней розмірностей k, k-1, k-2, …, 0, -1.

При d = 0, 1, 2, 3 відповідний симплекс є точкою, ребром, трикутником та трикутною пірамідою.

Наприклад, трикутна піраміда (3 грань) містить одну 3 грань (сама піраміда), чотири 2 грані (трикутники), шість 1 граней (ребра), чотири 0 граней (вершини) та одну (-1) грань (порожня множина), що разом складає 16 = 24 граней.

Означення. d політоп називається симпліциальним, якщо його кожна гіпергрань є симплексом.

Задача 1. Опукла оболонка. В Ed задано множину S, що містить N точок. Необхідно побудувати їх опуклу оболонку (повний опис границі CH (S)).

Задача 2. Крайні точки. В Ed задано множину S, що містить N точок. Необхідно визначити ті з них, які є вершинами опуклої оболонки conv (S).

Задача 3. Перевірка крайності точок площини. На площині задано N точок. Визначити, чи є вони вершинами своєї власної опуклої оболонки.

Теорема. Задача сортування зводиться за лінійний час до задачі побудови опуклої оболонки. Для знаходження впорядкованих N точок опуклої оболонки потрібен час O (N log N).

Доведення. Нехай дано N додатних дійсних чисел x1, x2, …, xN. Поставимо у відповідність точці xi точку (xi, xi+1) і присвоємо їй номер i. Утворені точки лежать на параболі y = x2. Опукла оболонка цієї множини точок буде складатися зі списку точок множини, впорядкованому за значенням абсциси.

S таких, що лежить на відкритому відрізку ab.

Множина E крайніх точок S представляє собою найменшу підмножину S, яка має властивість: conv (E) = conv (S), при чому Е в точності співпадає з множиною вершин conv (S).

Для знаходження опуклої оболонки скінченної множини необхідно виконати наступне:

1. Визначити крайні точки;

2. Впорядкувати ці точки так, щоб вони утворювали опуклий многокутник.

Теорема. Точка p не є крайньою плоскої опуклої множини S тоді і тільки тоді, коли вона лежить в деякому трикутнику, вершинами якого є точки з S, але сама вона не є вершиною цього трикутника.

Існує O (N3) трикутників, які визначаються N точками множини S. Отже за час O (N3) можна визначити, чи є задана точка крайньою. Повторення цієї процедури для всіх N точок множини S вимагає часу O (N4).

Точка P не є крайньою, оскільки вона лежить всередині трикутника P1P2P3.

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

Теорема. Послідовні вершини опуклого многокутника розташовані в порядку, якому відповідає зміна кута відносно довільної внутрішньої точки.

Теорема. В якості внутрішньої точки q можна взяти центроїд довільних трьох неколінеарних точок.

Для цього беруться дві довільні точки та шукається така третя точка з інших N — 2 точок, яка не лежить на прямій, що визначається першими двома.

Задача. На площині дано дві точки p1 та p2. Яка з цих точок має більший полярний кут?

p2 утворює з віссю Ох строго менший полярний кут, ніж p1 тоді і тільки тоді, коли трикутник (O, p2, p1) має строго додатню площу (або точка P1 лежить зліва від прямої OP2).

= Ѕ * (30 — 6) = 12.

Метод обхода Грехема Знайдемо внутрішню точку O множини точок S та перетворимо координати інших точок так, щоб знайдена внутрішня точка стала початком координат. Впорядкуємо лексикографічно N точок у відповідності зі значеннями полярного кута та відстані від початку координат (при цьому переводити координати точок до полярної системи координат не треба).

Алгоритм Грехема полягає в однократному перегляді впорядкованої послідовності точок, в процесі якої видаляються внутрішні точки. Перегляд починається з точки p0, в якості якої можна взяти саму праву (з максимальною абсцисою) з найменшою ординатою (вона точно належить опуклій оболонці). Послідовно перевіряються трійки точок p1p2p3, при чому.

1. Якщо трійка p1p2p3 утворює правий поворот, то видалити вершину p2 та перевірити трійку p0p1p3.

2. Якщо трійка p1p2p3 утворює лівий поворот, то продовжувати перегляд, перейшовши до трійки p2p3p4.

Оболонка Грехема.

1. Знайти внутрішню точку q.

2. Використовуючи q як початок координат, впорядкувати лексикографічно точки множини S у відповідності з полярним кутом та відстанню від q. Організувати точки множини у вигляді кільцевого списку із вказівниками NEXT, PREV та вказівником ПОЧАТОК на першу вершину. Значення TRUE логічної змінної f вказує на те, що вершина ПОЧАТОК досягнута при прямому русі по оболонці, а не в результаті повертання.

3. Обхід.

begin.

v xF0ACxF020ПОЧАТОК; w xF0ACxF020NEXT[v]; f xF0ACxF020FALSE;

while (NEXT[v] xF0B9xF020ПОЧАТОК or f = FALSE) do.

begin.

if NEXT[v] = w then f xF0ACTRUE;

if (три точки v, NEXT[v], NEXT[NEXT[v]] утворюють лівий поворот) then v xF0ACxF020NEXT[v];

else.

begin.

ВИДАЛИТИ NEXT[v];

v xF0ACxF020PREV[v];

end;

end;

end.

Теорема. Опукла оболонка N точок на площині може бути знайдена за час O (N * logN) при витратах пам’яті O (N).

Метод обхода Джарвіса Теорема. Відрізок l є ребром опуклої оболонки тоді і тільки тоді, коли всі інші точки заданої множини лежать на l або з одної сторони від нього.

прямих. Для кожної цієї прямої можна визначити за лінійний час розташування інших N-2 точок відносно цієї прямої, тим самим перевіривши чи задовільняє пряма умові теореми. За час O (N3) можна знайти всі пари точок, що визначають ребра опуклої оболонки та розташувати ці точки у вигляді списку послідовних вершин оболонки.

Джарвіс покращив цей алгоритм помітивши, що якщо відрізок pq є ребром оболонки, то повинно існувати інше ребро оболонки з кінцем в точці q. Нехай знайдено точку p1, яка належить опуклій оболонці (яка, наприклад, має максимальну х координату; а якщо таких точок декілька — то серед них взяти точку з мінімальною у координатою). Наступна точка p2 опуклої оболонки — це точка, яка має найменший додатний полярний кут відносно точки p1 як початку координат. І так далі шукаються наступні точки шляхом проходу вкругову опуклої оболонки, породжуючи у потрібному порядку послідовність крайніх точок, по одній на кожному кроці.

Обхід Джарвіса.

p[1] xF0ACxF020точка з найменшою y координатою;

p[2] xF0ACxF020точка з множини S, для якої кут між прямою p[2] - p[1] та віссю Ox найменший;

print (p[1], p[2]);

i xF0ACxF0202;

while (p[i] xF0B9xF020p[1]) do.

begin.

p[i + 1] xF0ACxF020точка з множини S, для якої кут p[i — 1] p[i] p[i + 1] є найбільшим;

i xF0ACxF020i + 1;

print (p[i]);

end.

Теорема. Часова оцінка обходу Джарвіса дорівнює O (N2).

Оскільки всі N точок можуть лежати на опуклій оболонці, а алгоритм Джарвіса вимагає лінійний час для знаходження кожної наступної точки оболонки, то в найгіршому випадку часова оцінка дорівнює O (N2). Обхід Джарвіса є ефективним, якщо кількість вершин опуклої оболонки h є малою у порівнянні зі значенням N — часова оцінка у цьому випадку дорівнюватиме O (N * h).

Алгоритм апроксимації опуклої оболонки При знаходженні наближеної опуклої оболонки ми розмінюємо точність на простоту та ефективність алгоритму.

Знайдемо мінімальне та максимальне значення х координати точок множини S та розіб'ємо вертикальну полосу між ними на k полос рівної ширини. В кожній із цих k полос шукаються дві точки, які мають мінімальну та максимальну у координату (обирається 2k точок). Обираються також точки з екстремальними значеннями х координати; якщо їх декілька, то обираються дві точки з екстремальними значеннями у координати (максимум обирається 4 точки). Обрана множина містить не більш ніж 2k + 4 точок і позначимо її через S*. Далі можна застосувати алгоритм Грехема побудови опуклої оболонки для множини точок S*.

Приклад. Множину точок S розбито на k = 4 полоси. В кожній полосі обрано дві точки. Для утвореної множини S* побудовано опуклу оболонку.

S, яка не попала всередину наближеної опуклої оболонки, знаходиться на відстані, не більшої за значення (xmax — xmin) / k.

Швидкі методи побудови опуклої оболонки Розіб'ємо множину S з N точок на дві підмножини, кожна з яких буде містити одну з двох ламаних, об'єднання яких дає многокутник опуклої оболонки. Початкове розбиття множини точок визначається прямою, що проходить через дві точки l та r, які мають відповідно найменшу та найбільшу абсцису. Позначимо через S1 підмножину точок, яка розташована вище або на прямій, а через S2 — підмножину точок, яка розташована нижче або на прямій. Якщо бути точним, то {S1, S2} не є розбиттям множини S, оскільки {l, r} xF0CExF020S1 xF0C7xF020S2. Далі множини S1 та S2 обробляються наступним чином (розглянемо на прикладі множини S1).

Знайдемо точку h, для якої трикутник lhr має максимальну площу серед усіх інших трикутників (якщо таких точок декілька, то обираємо ту, в якій кут hlr більший). Точка h гарантовано належить опуклій оболонці. Якщо провести через h пряму, паралельну lr, то над ній не буде жодної точки множини S. Якщо на цій прямій лежать декілька точок, то згідно з припущенням точка h буде самою лівою з них.

Будуємо дві прямі: L1 (сполучає точки l та h) та L2 (проходить через точки h та r). Для кожної точки множини S1 визначаємо її положення відносно цих прямих. Точки, які попали в трикутник lhr, можуть бути вилучені з подальшої обробки. Жодна з точок не знаходиться зліва від L1 та зліва від L2 (напрямки прямих вказано на рисунку). Точки, розташовані зліва від L1 чи на ній, утворюють множину S11. Аналогічно утворюється множина S12. Утворені множини S11 та S12 передаються далі на наступний рівень рекурсивної обробки.

Вибір початкових значень {l0, r0} точок l та r можна спростити. В якості l візьмемо точку (x0, y0), яка має найменшу абсцису, а в якості r візьмемо точку (x0, y0 — e), де e — мале додатне число. Вертикальна пряма, що проходить через l, буде першою прямою, яка розбиває множину точок S. Другою прямою буде пряма, що проходить через точки з екстремальними абсцисами.

Через * далі позначено операцію конкатенації списків.

Швидка опукла оболонка (S, l, r).

if (S = {l, r}) then return (l, r) /* опукла оболонка складається з єдиного орієнтованого ребра */.

else.

begin.

h xF0ACxF020сама дальня точка (S, l, r);

S1 xF0ACxF020точки множини S, розташовані зліва від прямої lh чи на ній;

S2 xF0ACxF020точки множини S, розташовані зліва від прямої hr чи на ній;

return Швидка опукла оболонка (S1, l, r) * (Швидка опукла оболонка (S2, h, r) — h);

end;

begin.

l0 xF0ACxF020(x0, y0) xF0ACxF020точка множини S з найменшою абсцисою;

r0 xF0ACxF020(x0, y0 — e);

Швидка опукла оболонка (S, l0, r0);

видалити точку r0 /* це еквівалентно тому, якщо покласти e = 0 */.

end.

Алгоритм типу розділяй та пануй Припустимо, що при розв’язку задачі побудови опуклої оболонки початкова множина точок S була розбита на дві частини S1 та S2, кожна з яких містить половину точок множини S. Якщо тепер рекурсивно знайти CH (S1) та CH (S2), то опуклу оболонку множини S можна знайти з рівності: CH (S1 xF0C8 S2) = CH (CH (S1) xF0C8 CH (S2)). При цьому треба пам’ятати, що CH (S1) та CH (S2) — це опуклі многокутники. Алгоритм розділяй та пануй має наступний вигляд:

1. Якщо |S| xF0A3xF020k (k — невелике ціле число), то побудувати опуклу оболонку одним із прямих методів та зупинитися; інакше перейти до кроку 2.

2. Розбити множину S довільним чином на дві приблизно рівні за потужністю множини S1 та S2.

3. Рекурсивно знайти опуклі оболонки CH (S1) та CH (S2).

4. Злити дві отримані оболонки, утворивши CH (S).

Задача. Опукла оболонка об'єднання опуклих многокутників. Дано два опуклих многокутника P1 та P2. Знайти опуклу оболонку їх об'єднання.

Алгоритм Шеймоса.

1. Знайти деяку внутрішню точку p многокутника P1 — наприклад, центроїд трьох довільних вершин P1. Ця точка буде внутрішньою точкою CH (P1 xF0C8 P2).

2. Визначити, чи є p внутрішньою точкою P2. Якщо p не є внутрішньою точкою P2, то перейти до кроку 4.

3. p є внутрішньою точкою P2. Вершини P1 та P2 є впорядкованими у відповідності зі значенням полярного кута відносно точки p. За час O (N) можна злити список вершин цих многокутників, отримавши впорядкований список вершин як P1, так і P2. Перейти до кроку 5.

4. p не є внутрішньою точкою P2. Якщо дивитися з точки p, то многокутник P2 лежить у кліні з кутом розвороту меншим чи рівним xF070. Цей клин визначається двома вершинами u та v многокутника P2, які можуть бути знайдені за лінійний час за один обхід вершин многокутника P2. Ці вершини розбивають границю P2 на два ланцюга вершин, які є монотонними відносно зміни полярного кута з початком в p. При русі по одному ланцюгу кут збільшується, при русі по другому — зменшується. Один з ланцюгів, який є опуклим по напрямку до точки p, може бути видалений, оскільки його вершини будуть внутрішніми точками CH (P1 xF0C8 P2). Другий ланцюг P2 та границю P1 можна злити в один впорядкований список (за полярним кутом відносно точки p) за лінійний час.

5. До отриманого впорядкованого списку вершин застосувати метод обходу Грехема, який вимагає лінійний час.

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

Означення. Опорною прямою до опуклого многокутника називається пряма l, яка проходить через деяку вершину многокутника P таким чином, що внутрішня частина P цілком знаходиться по одну сторону від l.

Побічним результатом описаного метода злиття є знаходження опорних прямих для двох опуклих многокутників. Два опуклих многокутника P1 та P2 з n та m вершинами відповідно, таких що один не лежить цілком всередині іншого, мають не більш ніж 2 * min (n, m) опорних прямих. Якщо вже отримано опуклу оболонку об'єднання P1 та P2, то опорні прямі обчислюються в результаті перегляду списку вершин CH (P1 xF0C8 P2).

Теорема. Кожна пара послідовних вершин CH (P1 xF0C8 P2), одна з яких належить P1, а друга P2, визначає опорну пряму.

Побудова опуклої оболонки простого многокутника Алгоритм Лі. Нехай p1 — сама ліва вершина заданого простого многокутника P, а (p1, p2, …, pN) — впорядкована циклічна послідовність його вершин (за вершиною pN йде p1). Внутрішність P залишається по праву сторону при обході його границі в указаному порядку. Нехай pM — сама права вершина. p1 та pM є граничними точками опуклої оболонки многокутника P. Вони розбивають послідовність вершин многокутника на два ланцюги: один від p1 до pM, другий — від pM до p1. Достатньо дослідити побудову опуклої оболонки для ланцюга (p1, p2, …, pM), яку будемо називати верхньою оболонкою.

Нехай (q1, q2, …, qR) — підпослідовність (p1, p2, …, pM), в якій q1 = p1 та qR = pM — шукана опукла оболонка многокутника. Кожне ребро qiqi+1 є «кришкою кармана» Ki, де карман Ki — це ланцюг послідовності (p1, p2, …, pM), першою та останньою вершинами якої є qi та qi+1 відповідно.

Алгоритм Лі проходить ланцюг та послідовно будує кришки усіх карманів. Критичною будемо називати вершину, яка з останньою знайденою вершиною типу q утворює карман. Але не кожна критична вершина належить кінцевій опуклій оболонці. Кроком просунення будемо називати перехід від однієї критичної вершини до іншої. Наприклад, на третьому кроці критичною точкою є p4. Наступною критичною точкою буде p7. При цьому критична точка p4 не належить опуклій оболонці.

1 крок 2 крок 3 крок 4 крок.

M) і вершина ps = qi є критичною. Позначимо через u вершину границі Р, яка є попередньою до qi. В залежності від положення u відносно орієнтованого відрізка qMqi мають місце два випадки:

1. Вершина u знаходиться справа від qMqi або на ньому. Тоді треба дослідити три області, які визначаються: прямою, що проходить через точки qi-1 та qi; промінем, який є продовженням відрізку qiu та частиною та частиною границі многокутника P, яка відповідає карману Ki-1.

2. Вершина u знаходиться зліва від qMqi. До дослідження треба додати четверту область.

Позначимо через v вершину, яка йде за qi на границі многокутника P. Ця вершина v може знаходитися в одній із областей, які визначено вище. В областях 2 та 3 вершина v буде критичною, в інших — ні. Дослідимо випадки розташування вершини v в кожній із цих областей.

Область 1. Границя многокутника заходить до карману. Рухаємося по границі до тих пір, поки не досягнемо першого ребра границі, одна з вершин w якого знаходиться зовні кармана (тобто в області 2). Це обов’язково відбудеться, оскільки многокутник простий.

Область 2. Шукається опорна пряма з вершини v до ланцюга (q1, q2, …, qi-1). Якщо ця пряма містить qr (r < i), то вершини (qr+1, qr+2, …, qi) видаляються, а v береться в якості нової qr+1.

Область 3. Вершина v є критичною і береться в якості qi+1.

Область 4. Границя многокутника заходить всередину опуклої оболонки. Як і в першому випадку будемо рухатися по границі многокутника до тих пір, поки не досягнемо першого ребра, яке має наступні властивості: одна з його вершин є зовнішньою по відношенню до області 4 або співпадає з qM.

Теорема. Опукла оболонка простого многокутника з N вершинами може бути побудована за оптимальний час O (N) з використанням пам’яті об'ємом O (N).

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

Означення. Часовий проміжок між вводом двох послідовних елементів даних називається затримкою надходження даних.

Задача. Відкритий алгоритм для опуклої оболонки. На площині задана послідовність N точок p1, p2, …, pN. Необхідно знайти їх опуклу оболонку таким чином, щоб після обробки точки pi була побудована CH (p1, p2, …, pi). Алгоритм повинен підтримувати деяке представлення поточної опуклої оболонки та коректувати його по мірі надходження точок.

Якщо не брати до уваги часову оцінку, то можна запропонувати наступний алгоритм:

1. Вводити точки поки не буде знайдено три неколінеарні точки. Їх центроїд буде внутрішньою точкою кінцевої опуклої оболонки, а отже підходить в якості початку координат, відносно якого визначаються полярні кути точок при сортуванні.

2. Підтримувати зв’язаний список впорядкованих крайніх точок. При надходженні точки pi вставити її у список відповідно до її полярного кута, витративши час O (i).

3. Виконати перегляд зв’язаного списку крайніх точокметодом Грехема. Можливі три варіанти цього кроку:

а) точка pi є крайньою і її включення викликає видалення деяких інших точок;

б) точка pi є крайньою, але її включення не викликає видалення інших точок;

в) точка pi є внутрішньою і тому вона видаляється.

Теорема. Довільний відкритий алгоритм побудови опуклої оболонки в найгіршому випадку повинен витрачувати на обробку між надходженням послідовних елементів даних час O (log N).

Ефективність відкритого алгоритму полягає у можливості швидко будувати дві опорні прямі до опуклого многокутника, що проходять через задану точку. Позначимо через Ci-1 опуклу оболонку множини {p1, p2, …, pi-1}. Необхідно побудувати з точки pi опорні прямі до Ci-1, якщо вони існують (коли pi є зовнішньою для Ci-1). Будемо називати опорну пряму лівою чи правою в залежності від того, по яку сторону вона знаходиться якщо дивитися з точки pi на Ci-1.

Означення. Вершина v називається вогнутою, якщо відрізок pv перетинає внутрішню частину многокутника. Якщо дві суміжні з v вершини лежать по одну сторону від прямої, що проходить через p та v, то вершина називається опорною. Інакше вершина називається опуклою.

Якщо v — опорна вершина, то розв’язок задачі завершується. Інакше будуємо опорні прямі. Для знаходження, наприклад, лівої опорної прямої, необхідно рухатися по вершинам многокутника проти чи за годинниковою стрілкою (в залежності від опуклості чи вогнутості вершини v). Таким чином визначаються дві опорні точки.

Теорема. Опукла оболонка множини з N точок на площині може бути побудована за допомогою відкритого алгоритму за час O (N * log N) з часом корекції O (log N).

v.

p + v.

p.

q.

p — q.

p.

u + v.

v.

u.

Aff (p, q, 0).

Aff (p, q, -½).

Aff (p, q, ½).

Aff (p, q, 1).

p.

q.

u.

p — q.

P.

Q.

r.

q.

p.

r.

q.

p.

r.

q.

p.

P2.

P.

P3.

P1.

P3.

P2.

P4.

q.

P1.

P5.

P6.

P1(3, 5).

P2(6, 2).

O.

P31.

P1.

P41.

P21.

P51.

P0.

P61.

P71.

P1.

L1.

S12.

S11.

h.

L2.

r.

l.

CH (S2).

CH (S1).

P2.

P1.

p.

P2.

P1.

v.

p.

u.

q4.

q5.

K4.

q3.

K3.

K2.

q2.

K5.

K1.

pM = qR.

p1 = q1.

p8.

p7 = q2.

p6.

p1 = q1.

p5.

p4.

p3.

p2.

p8.

p7.

p6.

p1 = q1.

p5.

p4 = q2.

p3.

p2.

p8.

p7.

p6.

p1 = q1.

p5.

p4.

p3 = q2.

p2.

p8.

p7.

p6.

p1 = q1.

p5.

p4.

p3.

p2 = q2.

qi.

qi-1.

u.

qM.

Ki-1.

qi.

qi-1.

u.

qM.

Ki-1.

qi.

qi-1.

w.

v.

u.

qM.

v = qr+1.

qi.

qi-1.

qr.

qM.

qi.

qi-1.

v = qi+1.

u.

qM.

qi.

qi-1.

w.

v.

u.

qM.

видаляється права опорна пряма ліва опорна пряма опорні точки.

Ci-1.

pi.

p.

p.

p.

v.

v.

v.

опукла опорна вогнута.