Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
В обчислювальній геометрії існує багато алгоритмів знаходження опуклої оболонки скінченної множини точок з різною складністю обчислень.
Обчислити опуклу оболонку означає, що виконане недвозначне та ефективне представлення необхідної опуклої форми. Обчислювальна складність відповідних алгоритмів зазвичай розраховується в термінах n — числа вхідних точок, та h — числа точок в опуклій оболонці.
Плоский випадок
Розглянемо загальний випадок, де вхідними даними алгоритму є скінченна невпорядкована множина точок декартової площини.
Якщо не всі точки лежать на одній прямій, їх опуклою оболонкою буде опуклий многокутник, вершини якого — це деякі точки зі вхідної множини. Найчастіше його подання є переліком вершин, відсортованих за годинниковою стрілкою або проти годинникової стрілки. В деяких випадках зручно представляти опуклий многокутник як перетин множини (півплощин) або півпросторів у просторовому випадку.
Нижня межа обчислювальної складності
відповідає точка на параболі з координатами 
. Таким чином задача побудови ОО еквівалентна задачі впорядкування точок.Для скінченої множини точок на площині нижня межа обчислювальної складності находження опуклої оболонки у вигляді опуклого многокутника є тією ж, що й в задачі сортування з подальшим зведенням. Це унаочнює такий приклад.
Для множини 
чисел, які треба відсортувати, розглянемо множину 
точок площини. Так як, вони лежать на параболі, яка є опуклою кривою, легко бачити, що вершини опуклої оболонки, що проходяться вздовж межі, створюють відсортовану множину чисел . Очевидно, для описаного перетворення чисел на точки і отримання їх відсортованого порядку потребується лінійний час. З цієї причини в загальному випадку опукла оболонка n точок не може бути обчислена швидше, ніж проведено їх сортування.
Стандартна Ω(n log n) нижня межа сортування доведена в обчислювальній моделі дерева прийняття рішень, в якому виконуються тільки порівняння, але не арифметичні дії; однак в цій моделі опуклі оболонки не можуть бути обчислені взагалі. Сортування також потребує час Ω(n log n) в обчислювальній моделі алгебраїчного дерева прийняття рішень, моделі, що більш підходить для опуклих оболонок, і в цих моделях опуклі оболонки також потребують час Ω(n log n). Однак в моделях комп'ютерної арифметики дозволяється сортувати числа швидше, ніж за час O(n log n), наприклад, при використанні алгоритмів цілочисельного сортування, пласкі опуклі оболонки також можуть бути обчислені швидше: Алгоритм Грехема для опуклих оболонок містить один крок сортування після якого йде лінійний об'єм додаткової роботи.
Оптимальні чутливі до вихідних даних алгоритми
Як зазначено вище, складність знаходження опуклої оболонки як функції вхідного розміру n обмежена знизу Ω(n log n). Однак складність деяких алгоритмів опуклої оболонки можна схарактеризувати як вхідним розміром n, так і вихідним розміром h (кількістю точок опуклої оболонки). Такі алгоритми називаються [en]. Вони можуть бути асимптотично ефективнішими, ніж алгоритми Θ(n log n) у випадках, коли h = o(n).
Відомо, що нижня межа часу роботи в найгіршому випадку алгоритмів чутливих до вихідних даних опуклої оболонки дорівнює Ω(n log h) у планарному випадку. Існує кілька алгоритмів, які досягають цієї оптимальної часової складності. Перший з таких алгоритмів був представлений [en] і [en] у 1986 році (які назвали його «алгоритмом крайньої опуклої оболонки»). Більш простий алгоритм був розроблений [en] у 1996 році та називається алгоритм Чена.
Алгоритми
Відомі алгоритми обчислення опуклої оболонки, наведені нижче, відсортовано за датою їх першої публікації. Обчислювальна складність кожного алгоритму наведена в термінах числа вхідних точок n і числа точок оболонки h. В найгіршому випадку h дорівнюватиме n.
- Алгоритм Джарвіса — O(nh)
Один з найпростіших (також з найефективнішим використанням часу в найгіршому випадку) плоских алгоритмів. Винайдений Чандом і Капуром в 1970 і Р. А. Джарвісом в 1973 роках. Він має обчислювальну складність O(nh). В найгіршому випадку обчислювальна складність складає O(n2).
- Алгоритм Грехема — O(n log n)
Дещо більш складний, але значно більш ефективний алгоритм, опублікований Рональдом Гремом в 1972 році. Якщо точки вже відсортовані за однією з координат о за кутом до фіксованого вектора, алгоритм потребує час O(n).
- Алгоритм швидкої оболонки
Винайдений незалежно в 1977 У. Едді та в 1978 А. Бікатом. Як алгоритм швидкого сортування має очікувану складність обчислень O(n log n), але може погіршуватися до Θ(nh) = O(n2) в найгіршому випадку.
- Розділяй і володарюй — O(n log n)
Інший O(n log n) алгоритм, опублікований в 1977 році Франко Препарата і Хонгом. Цей алгоритм є також придатним для тривимірного випадку.
- Монотонний ланцюг або Алгоритм Ендрю — O(n log n)
Опубліковано в 1979 А. М. Ендрю. Алгоритм можна розглядати як варіант алгоритму Грехема який сортує точки в лексикографічному порядку за їх координатами. В разі, якщо вхідні точки вже відсортовані, алгоритм потребує час O(n).
- Інкрементальний алгоритм обчислення опуклої оболонки — O(n log n)
Опубліковано в 1984 році М. Келей.
- Алгоритм Кіркпатрика — Зейделя — O(n log h)
Перший оптимальний чутливий до вихідних даних алгоритм, він використовує техніку «шлюб перед завоюванням». Опубліковано [en] і [en] в 1986.
- Алгоритм Чена — O(n log h)
Простіший оптимальний чутливий до вихідних даних алгоритм винайдений [en] в 1996 році.
Евристика Акла — Туссена
Наступна проста евристика часто використовується як перший крок у реалізації алгоритмів опуклої оболонки для підвищення їх продуктивності. Він заснований на ефективному алгоритмі опуклої оболонки [en] та [en], 1978 р. Мета алгоритма в тому, щоб швидко відкинути багато точок, які все одно не будуть частиною опуклої оболонки. Цей метод заснований на наступній ідеї. Знайдіть дві точки з найменшою та найбільшою координатами x, а також дві точки з найменшою та найбільшою y-координатами. Кожна з цих операцій займає O(n). Ці чотири точки утворюють опуклий чотирикутник, і всі точки, які лежать у цьому чотирикутнику (за винятком чотирьох початково обраних вершин), не є частиною опуклої оболонки. Знаходження всіх точок, які лежать у цьому чотирикутнику, також потребує O(n) операцій, а отже, загальна кількість операцій дорівнює O(n). За бажанням, точки з найменшою та найбільшою сумою координат x і y, а також точки з найменшою та найбільшою різницею x- і y-координат також можуть бути додані до чотирикутника, утворюючи таким чином неправильний опуклий восьмикутник, всередині якого можна безпечно відкинути всі точки. Якщо точки є випадковими величинами, то для обмеженого, але часто зустрічаємого класу функцій щільності ймовірності, цей одноразовий етап попередньої обробки, призведе до виконання алгоритму опуклої оболонки за лінійний очікуваний час, навіть якщо складність алгоритму опуклої оболонки є квадратичною відносно n.
Онлайн та динамічні задачі з опуклою оболонкою
Вище розглянуто випадок, коли всі вхідні точки відомі заздалегідь. Можемо розглянути два інших параметри.
- Онлайн-задача пошуку опуклої оболонки: вхідні точки надходять послідовно одна за одною. Після того, як кожна точка прибуває на вхід, опукла оболонка для мнодини точок, які отримані на цей час, має бути ефективно обчислена.
- Обслуговування динамічної опуклої оболонки: вхідні точки можна послідовно вставляти або видаляти, а опуклу оболонку необхідно оновлювати після кожної операції вставки/видалення.
Вставка точки може збільшити кількість вершин опуклої оболонки щонайбільше на 1, тоді як видалення може перетворити n-вершинну опуклу оболонку в (n-1) — вершину.
Онлайн-версію можна обробляти за час O(log n) на точку, що є асимптотично оптимальним. Динамічна версія може оброблятися за допомогою O(log2n) за операцію.
Простий багатокутник
Опукла оболонка простого многокутника ділиться багатокутником на частини, однією з яких є сам багатокутник, а решта — це «кишені», обмежені частиною межі многокутника та одним ребром оболонки. Хоча для задачі побудови опуклої оболонки простого багатокутника опубліковано багато алгоритмів, майже половина з них є невірними. Маккалум і Евіс надали перший правильний алгоритм. Пізніше спрощення, зроблене Гремом та Яо, (1983) і Лі, (1983) використовує лише одну структуру даних — стек. Їхній алгоритм обходить багатокутник за годинниковою стрілкою, починаючи з його крайньої лівої вершини. При цьому він зберігає послідовність тих вершин у стеку, які ще не були ідентифіковані як вершини у межах кишень. На кожному етапі алгоритм проходить шлях уздовж багатокутника від вершини стека до наступної вершини, яка не знаходиться в одній із двох кишень, суміжних з вершиною стека. Потім, поки дві верхні вершини в стеку разом з цією новою вершиною не знаходяться в опуклому положенні, вона виштовхує стек, перш ніж, нарешті, помістити у нього нову вершину. Коли обхід за годинниковою стрілкою досягає початкової точки, алгоритм повертає послідовність вершин стека як оболонку.
Вищі розмірності
Відомі алгоритми обчислення опуклої оболонки в тривимірному просторі, як і в просторах з довільною вимірністю. Наприклад, у випадках більших розмірностей можна застосовувати алгоритм Чена і алгоритм швидкої оболонки.
Для скінченної множини точок, опукла оболонка є опуклим багатогранником в тривимірному просторі і опуклим політопом для будь-якої кількості розмірностей, чиї вершини є точками з вхідної множини точок. Його представлення не є таким простим, як в плоскому випадку. У випадку більших розмірностей, навіть якщо відомі вершини опуклого політопу, побудова його граней є нетривіальною задачею, як і задача побудови вершин при наявних гранях. Об'єм вихідних даних є експоненціально більшим за об'єм вхідних даних і навіть у випадках, коли вхідні та вихідні дані мають порівняний об'єм, відомі алгоритми обчислення опуклої оболонки для віщих розмірностей не є [en] даних у відношенні до питань вироджених вхідних даних і проміжних результатів високої складності.
Див. також
Примітки
- Препарата, Шеймос, Обчислювальна геометрія, Глава «Опуклі оболонки: Базисні алгоритми»
- and , "A note on linear expected time algorithms for finding convex hulls, " Computing, Vol. 26, 1981, pp. 361—366.
- Aloupis, Greg. A History of Linear-time Convex Hull Algorithms for Simple Polygons. Процитовано 11 жовтня 2020.
- McCallum, Duncan; (1979), A linear algorithm for finding the convex hull of a simple polygon, , 9 (5): 201—206, doi:10.1016/0020-0190(79)90069-3, MR 0552534
- Graham, Ronald L.; (1983), Finding the convex hull of a simple polygon, , 4 (4): 324—331, doi:10.1016/0196-6774(83)90013-5, MR 0729228
- Lee, D. T. (1983), On finding the convex hull of a simple polygon, International Journal of Computer and Information Sciences, 12 (2): 87—98, doi:10.1007/BF00993195, MR 0724699
- See 's Конспект лекцій, в т.ч. Лекція 4 щодо останніх розробок, в т.ч. алгоритм Чена.
- Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1 грудня 1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software. 22 (4): 469—483. doi:10.1145/235815.235821.
- ; Bremner, David; (1997), How good are convex hull algorithms?, , 7 (5–6): 265—301, doi:10.1016/S0925-7721(96)00023-5.
Література
- Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. — М. : Мир, 1989. — 478 с. — .
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 33.3: Знаходження опуклої оболонки. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V obchislyuvalnij geometriyi isnuye bagato algoritmiv znahodzhennya opukloyi obolonki skinchennoyi mnozhini tochok z riznoyu skladnistyu obchislen Obchisliti opuklu obolonku oznachaye sho vikonane nedvoznachne ta efektivne predstavlennya neobhidnoyi opukloyi formi Obchislyuvalna skladnist vidpovidnih algoritmiv zazvichaj rozrahovuyetsya v terminah n chisla vhidnih tochok ta h chisla tochok v opuklij obolonci Ploskij vipadokRozglyanemo zagalnij vipadok de vhidnimi danimi algoritmu ye skinchenna nevporyadkovana mnozhina tochok dekartovoyi ploshini Yaksho ne vsi tochki lezhat na odnij pryamij yih opukloyu obolonkoyu bude opuklij mnogokutnik vershini yakogo ce deyaki tochki zi vhidnoyi mnozhini Najchastishe jogo podannya ye perelikom vershin vidsortovanih za godinnikovoyu strilkoyu abo proti godinnikovoyi strilki V deyakih vipadkah zruchno predstavlyati opuklij mnogokutnik yak peretin mnozhini pivploshin abo pivprostoriv u prostorovomu vipadku Nizhnya mezha obchislyuvalnoyi skladnosti Kozhnomu chislu xi displaystyle x i vidpovidaye tochka na paraboli z koordinatami xi xi2 displaystyle x i x i 2 Takim chinom zadacha pobudovi OO ekvivalentna zadachi vporyadkuvannya tochok Dlya skinchenoyi mnozhini tochok na ploshini nizhnya mezha obchislyuvalnoyi skladnosti nahodzhennya opukloyi obolonki u viglyadi opuklogo mnogokutnika ye tiyeyu zh sho j v zadachi sortuvannya z podalshim zvedennyam Ce unaochnyuye takij priklad Dlya mnozhini x1 xn displaystyle x 1 dots x n chisel yaki treba vidsortuvati rozglyanemo mnozhinu x1 x12 xn xn2 displaystyle x 1 x 1 2 dots x n x n 2 tochok ploshini Tak yak voni lezhat na paraboli yaka ye opukloyu krivoyu legko bachiti sho vershini opukloyi obolonki sho prohodyatsya vzdovzh mezhi stvoryuyut vidsortovanu mnozhinu chisel x1 xn displaystyle x 1 dots x n Ochevidno dlya opisanogo peretvorennya chisel na tochki i otrimannya yih vidsortovanogo poryadku potrebuyetsya linijnij chas Z ciyeyi prichini v zagalnomu vipadku opukla obolonka n tochok ne mozhe buti obchislena shvidshe nizh provedeno yih sortuvannya Standartna W n log n nizhnya mezha sortuvannya dovedena v obchislyuvalnij modeli dereva prijnyattya rishen v yakomu vikonuyutsya tilki porivnyannya ale ne arifmetichni diyi odnak v cij modeli opukli obolonki ne mozhut buti obchisleni vzagali Sortuvannya takozh potrebuye chas W n log n v obchislyuvalnij modeli algebrayichnogo dereva prijnyattya rishen modeli sho bilsh pidhodit dlya opuklih obolonok i v cih modelyah opukli obolonki takozh potrebuyut chas W n log n Odnak v modelyah komp yuternoyi arifmetiki dozvolyayetsya sortuvati chisla shvidshe nizh za chas O n log n napriklad pri vikoristanni algoritmiv cilochiselnogo sortuvannya plaski opukli obolonki takozh mozhut buti obchisleni shvidshe Algoritm Grehema dlya opuklih obolonok mistit odin krok sortuvannya pislya yakogo jde linijnij ob yem dodatkovoyi roboti Optimalni chutlivi do vihidnih danih algoritmi Yak zaznacheno vishe skladnist znahodzhennya opukloyi obolonki yak funkciyi vhidnogo rozmiru n obmezhena znizu W n log n Odnak skladnist deyakih algoritmiv opukloyi obolonki mozhna sharakterizuvati yak vhidnim rozmirom n tak i vihidnim rozmirom h kilkistyu tochok opukloyi obolonki Taki algoritmi nazivayutsya en Voni mozhut buti asimptotichno efektivnishimi nizh algoritmi 8 n log n u vipadkah koli h o n Vidomo sho nizhnya mezha chasu roboti v najgirshomu vipadku algoritmiv chutlivih do vihidnih danih opukloyi obolonki dorivnyuye W n log h u planarnomu vipadku Isnuye kilka algoritmiv yaki dosyagayut ciyeyi optimalnoyi chasovoyi skladnosti Pershij z takih algoritmiv buv predstavlenij en i en u 1986 roci yaki nazvali jogo algoritmom krajnoyi opukloyi obolonki Bilsh prostij algoritm buv rozroblenij en u 1996 roci ta nazivayetsya algoritm Chena Algoritmi Vidomi algoritmi obchislennya opukloyi obolonki navedeni nizhche vidsortovano za datoyu yih pershoyi publikaciyi Obchislyuvalna skladnist kozhnogo algoritmu navedena v terminah chisla vhidnih tochok n i chisla tochok obolonki h V najgirshomu vipadku h dorivnyuvatime n Algoritm Dzharvisa O nh Odin z najprostishih takozh z najefektivnishim vikoristannyam chasu v najgirshomu vipadku ploskih algoritmiv Vinajdenij Chandom i Kapurom v 1970 i R A Dzharvisom v 1973 rokah Vin maye obchislyuvalnu skladnist O nh V najgirshomu vipadku obchislyuvalna skladnist skladaye O n2 Algoritm Grehema O n log n Desho bilsh skladnij ale znachno bilsh efektivnij algoritm opublikovanij Ronaldom Gremom v 1972 roci Yaksho tochki vzhe vidsortovani za odniyeyu z koordinat o za kutom do fiksovanogo vektora algoritm potrebuye chas O n Algoritm shvidkoyi obolonki Vinajdenij nezalezhno v 1977 U Eddi ta v 1978 A Bikatom Yak algoritm shvidkogo sortuvannya maye ochikuvanu skladnist obchislen O n log n ale mozhe pogirshuvatisya do 8 nh O n2 v najgirshomu vipadku Rozdilyaj i volodaryuj O n log n Inshij O n log n algoritm opublikovanij v 1977 roci Franko Preparata i Hongom Cej algoritm ye takozh pridatnim dlya trivimirnogo vipadku Monotonnij lancyug abo Algoritm Endryu O n log n Opublikovano v 1979 A M Endryu Algoritm mozhna rozglyadati yak variant algoritmu Grehema yakij sortuye tochki v leksikografichnomu poryadku za yih koordinatami V razi yaksho vhidni tochki vzhe vidsortovani algoritm potrebuye chas O n Inkrementalnij algoritm obchislennya opukloyi obolonki O n log n Opublikovano v 1984 roci M Kelej Algoritm Kirkpatrika Zejdelya O n log h Pershij optimalnij chutlivij do vihidnih danih algoritm vin vikoristovuye tehniku shlyub pered zavoyuvannyam Opublikovano en i en v 1986 Algoritm Chena O n log h Prostishij optimalnij chutlivij do vihidnih danih algoritm vinajdenij en v 1996 roci Evristika Akla Tussena Nastupna prosta evristika chasto vikoristovuyetsya yak pershij krok u realizaciyi algoritmiv opukloyi obolonki dlya pidvishennya yih produktivnosti Vin zasnovanij na efektivnomu algoritmi opukloyi obolonki en ta en 1978 r Meta algoritma v tomu shob shvidko vidkinuti bagato tochok yaki vse odno ne budut chastinoyu opukloyi obolonki Cej metod zasnovanij na nastupnij ideyi Znajdit dvi tochki z najmenshoyu ta najbilshoyu koordinatami x a takozh dvi tochki z najmenshoyu ta najbilshoyu y koordinatami Kozhna z cih operacij zajmaye O n Ci chotiri tochki utvoryuyut opuklij chotirikutnik i vsi tochki yaki lezhat u comu chotirikutniku za vinyatkom chotiroh pochatkovo obranih vershin ne ye chastinoyu opukloyi obolonki Znahodzhennya vsih tochok yaki lezhat u comu chotirikutniku takozh potrebuye O n operacij a otzhe zagalna kilkist operacij dorivnyuye O n Za bazhannyam tochki z najmenshoyu ta najbilshoyu sumoyu koordinat x i y a takozh tochki z najmenshoyu ta najbilshoyu rizniceyu x i y koordinat takozh mozhut buti dodani do chotirikutnika utvoryuyuchi takim chinom nepravilnij opuklij vosmikutnik vseredini yakogo mozhna bezpechno vidkinuti vsi tochki Yaksho tochki ye vipadkovimi velichinami to dlya obmezhenogo ale chasto zustrichayemogo klasu funkcij shilnosti jmovirnosti cej odnorazovij etap poperednoyi obrobki prizvede do vikonannya algoritmu opukloyi obolonki za linijnij ochikuvanij chas navit yaksho skladnist algoritmu opukloyi obolonki ye kvadratichnoyu vidnosno n Onlajn ta dinamichni zadachi z opukloyu obolonkoyu Vishe rozglyanuto vipadok koli vsi vhidni tochki vidomi zazdalegid Mozhemo rozglyanuti dva inshih parametri Onlajn zadacha poshuku opukloyi obolonki vhidni tochki nadhodyat poslidovno odna za odnoyu Pislya togo yak kozhna tochka pribuvaye na vhid opukla obolonka dlya mnodini tochok yaki otrimani na cej chas maye buti efektivno obchislena Obslugovuvannya dinamichnoyi opukloyi obolonki vhidni tochki mozhna poslidovno vstavlyati abo vidalyati a opuklu obolonku neobhidno onovlyuvati pislya kozhnoyi operaciyi vstavki vidalennya Vstavka tochki mozhe zbilshiti kilkist vershin opukloyi obolonki shonajbilshe na 1 todi yak vidalennya mozhe peretvoriti n vershinnu opuklu obolonku v n 1 vershinu Onlajn versiyu mozhna obroblyati za chas O log n na tochku sho ye asimptotichno optimalnim Dinamichna versiya mozhe obroblyatisya za dopomogoyu O log2n za operaciyu Prostij bagatokutnik Dokladnishe en Opukla obolonka prostogo mnogokutnika dilitsya bagatokutnikom na chastini odniyeyu z yakih ye sam bagatokutnik a reshta ce kisheni obmezheni chastinoyu mezhi mnogokutnika ta odnim rebrom obolonki Hocha dlya zadachi pobudovi opukloyi obolonki prostogo bagatokutnika opublikovano bagato algoritmiv majzhe polovina z nih ye nevirnimi Makkalum i Evis nadali pershij pravilnij algoritm Piznishe sproshennya zroblene Gremom ta Yao 1983 i Li 1983 vikoristovuye lishe odnu strukturu danih stek Yihnij algoritm obhodit bagatokutnik za godinnikovoyu strilkoyu pochinayuchi z jogo krajnoyi livoyi vershini Pri comu vin zberigaye poslidovnist tih vershin u steku yaki she ne buli identifikovani yak vershini u mezhah kishen Na kozhnomu etapi algoritm prohodit shlyah uzdovzh bagatokutnika vid vershini steka do nastupnoyi vershini yaka ne znahoditsya v odnij iz dvoh kishen sumizhnih z vershinoyu steka Potim poki dvi verhni vershini v steku razom z ciyeyu novoyu vershinoyu ne znahodyatsya v opuklomu polozhenni vona vishtovhuye stek persh nizh nareshti pomistiti u nogo novu vershinu Koli obhid za godinnikovoyu strilkoyu dosyagaye pochatkovoyi tochki algoritm povertaye poslidovnist vershin steka yak obolonku Vishi rozmirnostiVidomi algoritmi obchislennya opukloyi obolonki v trivimirnomu prostori yak i v prostorah z dovilnoyu vimirnistyu Napriklad u vipadkah bilshih rozmirnostej mozhna zastosovuvati algoritm Chena i algoritm shvidkoyi obolonki Dlya skinchennoyi mnozhini tochok opukla obolonka ye opuklim bagatogrannikom v trivimirnomu prostori i opuklim politopom dlya bud yakoyi kilkosti rozmirnostej chiyi vershini ye tochkami z vhidnoyi mnozhini tochok Jogo predstavlennya ne ye takim prostim yak v ploskomu vipadku U vipadku bilshih rozmirnostej navit yaksho vidomi vershini opuklogo politopu pobudova jogo granej ye netrivialnoyu zadacheyu yak i zadacha pobudovi vershin pri nayavnih granyah Ob yem vihidnih danih ye eksponencialno bilshim za ob yem vhidnih danih i navit u vipadkah koli vhidni ta vihidni dani mayut porivnyanij ob yem vidomi algoritmi obchislennya opukloyi obolonki dlya vishih rozmirnostej ne ye en danih u vidnoshenni do pitan virodzhenih vhidnih danih i promizhnih rezultativ visokoyi skladnosti Div takozhZadacha dinamichnoyi pidtrimki opukloyi obolonki Ortogonalna opukla obolonkaPrimitkiPreparata Shejmos Obchislyuvalna geometriya Glava Opukli obolonki Bazisni algoritmi and A note on linear expected time algorithms for finding convex hulls Computing Vol 26 1981 pp 361 366 Aloupis Greg A History of Linear time Convex Hull Algorithms for Simple Polygons Procitovano 11 zhovtnya 2020 McCallum Duncan 1979 A linear algorithm for finding the convex hull of a simple polygon 9 5 201 206 doi 10 1016 0020 0190 79 90069 3 MR 0552534 Graham Ronald L 1983 Finding the convex hull of a simple polygon 4 4 324 331 doi 10 1016 0196 6774 83 90013 5 MR 0729228 Lee D T 1983 On finding the convex hull of a simple polygon International Journal of Computer and Information Sciences 12 2 87 98 doi 10 1007 BF00993195 MR 0724699 See s Konspekt lekcij v t ch Lekciya 4 shodo ostannih rozrobok v t ch algoritm Chena Barber C Bradford Dobkin David P Huhdanpaa Hannu 1 grudnya 1996 The quickhull algorithm for convex hulls ACM Transactions on Mathematical Software 22 4 469 483 doi 10 1145 235815 235821 Bremner David 1997 How good are convex hull algorithms 7 5 6 265 301 doi 10 1016 S0925 7721 96 00023 5 LiteraturaPreparata F Shejmos M Vychislitelnaya geometriya Vvedenie M Mir 1989 478 s ISBN 5 03 001041 6 T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 33 3 Znahodzhennya opukloyi obolonki Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4