Considerați cazul general în care intrarea algoritmului este un set finit neordonat de puncte pe un plan cartezian. Un caz special important, în care punctele sunt date în ordinea traversării limitei unui poligon simplu, este descris mai târziu într-o subsecțiune separată.
Dacă nu toate punctele sunt pe aceeași dreaptă, atunci coca convexă a acestora este un poligon convex ale cărui vârfuri sunt unele dintre punctele din setul de intrare. Cea mai obișnuită reprezentare a sa este lista de vârfuri ordonate de-a lungul limitei sale în sensul acelor de ceasornic sau în sens invers. În unele aplicații este convenabil să se reprezinte un poligon convex ca o intersecție a unui set de semiplane.
Limita inferioară a complexității de calculEdit
Pentru un set finit de puncte din plan, se poate demonstra cu ușurință că limita inferioară a complexității de calcul pentru găsirea coca convexă reprezentată ca un poligon convex este aceeași cu cea pentru sortare, folosind următoarea reducere. Pentru setul x 1 , … , … , x n {\displaystyle x_{1},\dots ,x_{n}}
numere pentru sortare se consideră setul de puncte ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
de puncte din plan. Deoarece acestea se află pe o parabolă, care este o curbă convexă, este ușor de văzut că vârfurile corpului convex, atunci când sunt parcurse de-a lungul limitei, produc ordinea ordonată a numerelor x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}}
. În mod evident, este necesar un timp liniar pentru transformarea descrisă a numerelor în puncte și apoi pentru extragerea ordinii lor ordonate. Prin urmare, în cazul general, coca convexă a n puncte nu poate fi calculată mai repede decât sortarea.
Limita inferioară standard Ω(n log n) pentru sortare este demonstrată în modelul arborelui de decizie al calculului, în care se pot efectua numai comparații numerice, dar nu și operații aritmetice; cu toate acestea, în acest model, coca convexă nu poate fi calculată deloc. Sortarea necesită, de asemenea, timp Ω(n log n) în modelul arborelui decizional algebric de calcul, un model care este mai potrivit pentru coifurile convexe, iar în acest model coifurile convexe necesită, de asemenea, timp Ω(n log n). Cu toate acestea, în modelele de aritmetică informatică care permit sortarea numerelor mai rapid decât timpul O(n log n), de exemplu prin utilizarea algoritmilor de sortare a numerelor întregi, coca convexă plană poate fi, de asemenea, calculată mai rapid: algoritmul de scanare Graham pentru coca convexă constă într-o singură etapă de sortare urmată de o cantitate liniară de muncă suplimentară.
Algoritmi optimi sensibili la ieșireEdit
După cum s-a afirmat mai sus, complexitatea găsirii unui hull convex în funcție de mărimea intrării n este mărginită inferior de Ω(n log n). Cu toate acestea, complexitatea unor algoritmi de găsire a unei coifuri convexe poate fi caracterizată atât în funcție de dimensiunea de intrare n, cât și de dimensiunea de ieșire h (numărul de puncte din coif). Astfel de algoritmi se numesc algoritmi sensibili la ieșire. Aceștia pot fi asimptotic mai eficienți decât algoritmii Θ(n log n) în cazurile în care h = o(n).
Limita inferioară a timpului de execuție în cel mai rău caz al algoritmilor de coif convex sensibili la ieșire a fost stabilită ca fiind Ω(n log h) în cazul planar. Există mai mulți algoritmi care ating această complexitate optimă a timpului. Cel mai timpuriu a fost introdus de Kirkpatrick și Seidel în 1986 (care l-au numit „algoritmul suprem al corpului convex”). Un algoritm mult mai simplu a fost dezvoltat de Chan în 1996 și se numește algoritmul lui Chan.
AlgoritmiEdit
Algoritmii cunoscuți ai corpului convex sunt enumerați mai jos, ordonați în funcție de data primei publicații. Complexitatea în timp a fiecărui algoritm este precizată în funcție de numărul de puncte de intrare n și de numărul de puncte de pe cocă h. Rețineți că, în cel mai rău caz, h poate fi la fel de mare ca n.
- Gift wrapping, a.k.a. Jarvis march – O(nh)
Unul dintre cei mai simpli (deși nu cel mai eficient în timp în cel mai rău caz) algoritmi planari. Creat independent de Chand & Kapur în 1970 și de R. A. Jarvis în 1973. Are o complexitate în timp O(nh), unde n este numărul de puncte din set, iar h este numărul de puncte din hull. În cel mai rău caz, complexitatea este Θ(n2). - Graham scan – O(n log n)
Un algoritm puțin mai sofisticat, dar mult mai eficient, publicat de Ronald Graham în 1972. Dacă punctele sunt deja sortate după una dintre coordonate sau după unghiul față de un vector fix, atunci algoritmul durează O(n). - Quickhull
Creat independent în 1977 de W. Eddy și în 1978 de A. Bykat. La fel ca și algoritmul quicksort, are o complexitate în timp așteptată de O(n log n), dar poate degenera la O(n2) în cel mai rău caz. - Divide și cucerește – O(n log n)
Un alt algoritm O(n log n), publicat în 1977 de Preparata și Hong. Acest algoritm este aplicabil și în cazul tridimensional. - Lanț monoton, cunoscut și ca algoritmul lui Andrew- O(n log n)
Publicat în 1979 de A. M. Andrew. Algoritmul poate fi văzut ca o variantă a scanării Graham care ordonează lexicografic punctele în funcție de coordonatele lor. Atunci când datele de intrare sunt deja sortate, algoritmul are nevoie de timp O(n). - Algoritmul incremental convex hull – O(n log n)
Publicat în 1984 de Michael Kallay. - Algoritmul Kirkpatrick-Seidel – O(n log h)
Primul algoritm optim sensibil la ieșire. Modifică algoritmul divide și cucerește folosind tehnica căsătoriei înainte de cucerire și programarea liniară cu dimensiuni reduse. Publicat de Kirkpatrick și Seidel în 1986. - Algoritmul lui Chan – O(n log h)
Un algoritm optim mai simplu, sensibil la ieșire, creat de Chan în 1996. Acesta combină împachetarea cadourilor cu executarea unui algoritm O(n log n) (cum ar fi scanarea Graham) pe subansambluri mici ale datelor de intrare.
Heuristica Akl-ToussaintEdit
Următoarea euristică simplă este adesea folosită ca prim pas în implementările algoritmilor de coifuri convexe pentru a le îmbunătăți performanța. Ea se bazează pe algoritmul eficient al corpului convex al lui Selim Akl și G. T. Toussaint, 1978. Ideea este de a exclude rapid multe puncte care oricum nu ar face parte din coca convexă. Această metodă se bazează pe următoarea idee. Găsiți cele două puncte cu cele mai mici și cele mai mari coordonate x, precum și cele două puncte cu cele mai mici și cele mai mari coordonate y. (Fiecare dintre aceste operații durează O(n).) Aceste patru puncte formează un cvadrilateral convex, iar toate punctele care se află în acest cvadrilateral (cu excepția celor patru vârfuri alese inițial) nu fac parte din coca convexă. Găsirea tuturor acestor puncte care se află în acest cvadrilateral este, de asemenea, O(n) și, prin urmare, întreaga operațiune este O(n). Opțional, punctele cu cea mai mică și cea mai mare sumă a coordonatelor x și y, precum și cele cu cea mai mică și cea mai mare diferență a coordonatelor x și y pot fi, de asemenea, adăugate la cvadrilaterală, formând astfel un octogon convex neregulat, ale cărui părți interioare pot fi eliminate în siguranță. Dacă punctele sunt variabile aleatoare, atunci, pentru o clasă restrânsă, dar frecvent întâlnită, de funcții de densitate de probabilitate, această etapă de preprocesare de aruncat va face ca un algoritm de coif convex să ruleze în timp liniar așteptat, chiar dacă complexitatea în cel mai rău caz a algoritmului de coif convex este pătratică în n.
Probleme de coif convex on-line și dinamiceEdit
Discuția de mai sus ia în considerare cazul în care toate punctele de intrare sunt cunoscute în avans. Se pot lua în considerare alte două setări.
- Online convex hull problem: Punctele de intrare sunt obținute secvențial, unul câte unul. După ce fiecare punct ajunge la intrare, trebuie să se calculeze eficient coca convexă pentru setul de puncte obținut până atunci.
- Întreținerea dinamică a coca convexă: Punctele de intrare pot fi inserate sau șterse secvențial, iar coca convexă trebuie actualizată după fiecare operațiune de inserție/ștergere.
Inserția unui punct poate crește numărul de vârfuri ale coca convexă cel mult cu 1, în timp ce ștergerea poate transforma o coca convexă cu n-vârfuri într-una cu n-1-vârfuri.
Versiunea online poate fi tratată cu O(log n) pe punct, care este optimă asimptotic. Versiunea dinamică poate fi gestionată cu O(log2 n) per operație.
Poligon simpluEdit
Coaja convexă a unui poligon simplu este împărțită de poligon în bucăți, dintre care una este poligonul însuși, iar restul sunt buzunare delimitate de o bucată din limita poligonului și de o singură muchie a cocii. Deși au fost publicați mulți algoritmi pentru problema construirii corpului convex al unui poligon simplu, aproape jumătate dintre ei sunt incorecți.McCallum și Avis au furnizat primul algoritm corect.O simplificare ulterioară realizată de Graham & Yao (1983) și Lee (1983) utilizează doar o singură structură de date cu stivă. Algoritmul lor parcurge poligonul în sensul acelor de ceasornic, pornind de la cel mai din stânga vârf al acestuia. Pe măsură ce face acest lucru, el stochează o secvență convexă de vârfuri pe stivă, cele care nu au fost încă identificate ca fiind în interiorul buzunarelor. La fiecare pas, algoritmul urmează o cale de-a lungul poligonului, de la vârful stivei până la următorul vârf care nu se află într-unul dintre cele două buzunare adiacente vârfului stivei. Apoi, în timp ce primele două vârfuri de pe stivă împreună cu acest nou vârf nu se află în poziție convexă, se deschide stiva, înainte de a împinge în cele din urmă noul vârf pe stivă. Când parcurgerea în sensul acelor de ceasornic ajunge la punctul de plecare, algoritmul returnează secvența de vârfuri din stivă ca fiind coca.
.