Consideriamo il caso generale quando l’input dell’algoritmo è un insieme finito e non ordinato di punti su un piano cartesiano. Un importante caso speciale, in cui i punti sono dati nell’ordine di attraversamento del confine di un poligono semplice, è descritto più avanti in una sottosezione separata.
Se non tutti i punti sono sulla stessa linea, allora il loro guscio convesso è un poligono convesso i cui vertici sono alcuni dei punti nell’insieme di input. La sua rappresentazione più comune è la lista dei suoi vertici ordinati lungo il suo confine in senso orario o antiorario. In alcune applicazioni è conveniente rappresentare un poligono convesso come intersezione di un insieme di semipiani.
Limite inferiore della complessità computazionaleModifica
Per un insieme finito di punti nel piano il limite inferiore della complessità computazionale di trovare il guscio convesso rappresentato come un poligono convesso è facilmente dimostrato essere lo stesso dell’ordinamento usando la seguente riduzione. Per l’insieme x 1 , … , x n {displaystyle x_{1},\punti ,x_{n}}
numeri da ordinare considerare l’insieme dei punti ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\punti ,(x_{n},x_{n}^{2})}
di punti nel piano. Poiché essi giacciono su una parabola, che è una curva convessa, è facile vedere che i vertici della carena convessa, quando vengono attraversati lungo il confine, producono l’ordine ordinato dei numeri x 1 , … , x n {\displaystyle x_{1},\punti ,x_{n}}
. Chiaramente, il tempo lineare è richiesto per la trasformazione descritta dei numeri in punti e poi per estrarre il loro ordine ordinato. Pertanto, nel caso generale, la carena convessa di n punti non può essere calcolata più rapidamente dell’ordinamento.
Il limite inferiore standard di Ω(n log n) per l’ordinamento è dimostrato nel modello di calcolo ad albero decisionale, in cui si possono eseguire solo confronti numerici ma non operazioni aritmetiche; tuttavia, in questo modello, le carene convesse non possono essere calcolate affatto. L’ordinamento richiede anche tempo Ω(n log n) nel modello algebrico di albero decisionale di calcolo, un modello che è più adatto per i convex hulls, e in questo modello i convex hulls richiedono anche tempo Ω(n log n). Tuttavia, nei modelli di aritmetica del computer che permettono di ordinare i numeri più rapidamente del tempo O(n log n), per esempio utilizzando algoritmi di ordinamento interi, le carene convesse planari possono anche essere calcolate più rapidamente: l’algoritmo di scansione Graham per le carene convesse consiste in un singolo passo di ordinamento seguito da una quantità lineare di lavoro aggiuntivo.
Algoritmi ottimali sensibili all’outputModifica
Come detto sopra, la complessità di trovare un guscio convesso in funzione della dimensione n dell’input è limitata in basso da Ω(n log n). Tuttavia, la complessità di alcuni algoritmi di carena convessa può essere caratterizzata in termini sia della dimensione dell’input n che della dimensione dell’output h (il numero di punti nella carena). Tali algoritmi sono chiamati algoritmi sensibili all’output. Possono essere asintoticamente più efficienti degli algoritmi Θ(n log n) nei casi in cui h = o(n).
Il limite inferiore del tempo di esecuzione nel caso peggiore degli algoritmi convessi sensibili all’uscita è stato stabilito essere Ω(n log h) nel caso planare. Ci sono diversi algoritmi che raggiungono questa complessità temporale ottimale. Il primo è stato introdotto da Kirkpatrick e Seidel nel 1986 (che l’hanno chiamato “l’ultimo algoritmo a carena convessa”). Un algoritmo molto più semplice è stato sviluppato da Chan nel 1996, ed è chiamato algoritmo di Chan.
AlgoritmiModifica
Gli algoritmi a carena convessa conosciuti sono elencati di seguito, ordinati per data di prima pubblicazione. La complessità temporale di ogni algoritmo è dichiarata in termini di numero di punti di input n e numero di punti sulla carena. Si noti che nel caso peggiore h può essere grande quanto n.
- Gift wrapping, a.k.a. Jarvis march – O(nh)
Uno dei più semplici (sebbene non il più efficiente in termini di tempo nel caso peggiore) algoritmi planari. Creato indipendentemente da Chand & Kapur nel 1970 e da R. A. Jarvis nel 1973. Ha una complessità temporale O(nh), dove n è il numero di punti nell’insieme e h è il numero di punti nello scafo. Nel caso peggiore la complessità è Θ(n2). - Graham scan – O(n log n)
Un algoritmo leggermente più sofisticato, ma molto più efficiente, pubblicato da Ronald Graham nel 1972. Se i punti sono già ordinati per una delle coordinate o per l’angolo rispetto a un vettore fisso, allora l’algoritmo impiega O(n) tempo. - Quickhull
Creato indipendentemente nel 1977 da W. Eddy e nel 1978 da A. Bykat. Proprio come l’algoritmo quicksort, ha la complessità temporale prevista di O(n log n), ma può degenerare a O(n2) nel caso peggiore. - Divide and conquer – O(n log n)
Un altro algoritmo O(n log n), pubblicato nel 1977 da Preparata e Hong. Questo algoritmo è applicabile anche al caso tridimensionale. - Catena monotona, alias algoritmo di Andrew- O(n log n)
Pubblicato nel 1979 da A. M. Andrew. L’algoritmo può essere visto come una variante della scansione di Graham che ordina i punti in modo lessicografico secondo le loro coordinate. Quando l’input è già ordinato, l’algoritmo impiega O(n) tempo. - Algoritmo incrementale a scafo convesso – O(n log n)
Pubblicato nel 1984 da Michael Kallay. - Algoritmo di Kirkpatrick-Seidel – O(n log h)
Il primo algoritmo ottimale sensibile all’output. Modifica l’algoritmo divide et impera utilizzando la tecnica del marriage-before-conquest e la programmazione lineare a bassa dimensione. Pubblicato da Kirkpatrick e Seidel nel 1986. - Algoritmo di Chan – O(n log h)
Un algoritmo ottimale sensibile all’uscita più semplice creato da Chan nel 1996. Combina il gift wrapping con l’esecuzione di un algoritmo O(n log n) (come Graham scan) su piccoli sottoinsiemi dell’input.
Euristica di Akl-ToussaintEdit
La seguente semplice euristica è spesso usata come primo passo nelle implementazioni degli algoritmi a scafo convesso per migliorarne le prestazioni. Si basa sull’efficiente algoritmo del guscio convesso di Selim Akl e G. T. Toussaint, 1978. L’idea è di escludere rapidamente molti punti che non farebbero comunque parte dello scafo convesso. Questo metodo si basa sulla seguente idea. Trovare i due punti con le coordinate x più basse e più alte, e i due punti con le coordinate y più basse e più alte. (Ognuna di queste operazioni richiede O(n)). Questi quattro punti formano un quadrilatero convesso, e tutti i punti che giacciono in questo quadrilatero (tranne i quattro vertici scelti inizialmente) non fanno parte del guscio convesso. Trovare tutti questi punti che giacciono in questo quadrilatero è anche O(n), e quindi, l’intera operazione è O(n). Opzionalmente, i punti con le somme più piccole e più grandi delle coordinate x e y e quelli con le differenze più piccole e più grandi delle coordinate x e y possono anche essere aggiunti al quadrilatero, formando così un ottagono convesso irregolare, il cui interno può essere tranquillamente scartato. Se i punti sono variabili casuali, allora per una classe ristretta ma comunemente incontrata di funzioni di densità di probabilità, questo passo di pre-elaborazione a perdere farà funzionare un algoritmo a carena convessa in tempo lineare atteso, anche se la complessità del caso peggiore dell’algoritmo a carena convessa è quadratica in n.
Problemi a carena convessa on-line e dinamiciModifica
La discussione precedente considera il caso in cui tutti i punti di input sono noti in anticipo. Si possono considerare altre due impostazioni.
- Problema della carena convessa online: i punti di input sono ottenuti sequenzialmente uno per uno. Dopo che ogni punto arriva in input, la carena convessa per l’insieme di punti ottenuti finora deve essere calcolata in modo efficiente.
- Manutenzione dinamica della carena convessa: I punti di input possono essere inseriti o cancellati in modo sequenziale, e la carena convessa deve essere aggiornata dopo ogni operazione di inserimento/cancellazione.
L’inserimento di un punto può aumentare il numero di vertici di una carena convessa al massimo di 1, mentre la cancellazione può convertire una carena convessa a n vertici in una a n-1 vertici.
La versione online può essere gestita con O(log n) per punto, che è asintoticamente ottimale. La versione dinamica può essere gestita con O(log2 n) per operazione.
Poligono sempliceModifica
La carena convessa di un poligono semplice è divisa dal poligono in pezzi, uno dei quali è il poligono stesso e il resto sono tasche delimitate da un pezzo del confine del poligono e un singolo bordo della carena. Sebbene siano stati pubblicati molti algoritmi per il problema della costruzione della carena convessa di un poligono semplice, quasi la metà di essi sono errati.McCallum e Avis hanno fornito il primo algoritmo corretto.Una successiva semplificazione di Graham & Yao (1983) e Lee (1983) utilizza solo una singola struttura dati stack. Il loro algoritmo attraversa il poligono in senso orario, partendo dal suo vertice più a sinistra. Mentre lo fa, memorizza una sequenza convessa di vertici sulla pila, quelli che non sono ancora stati identificati come appartenenti alle tasche. Ad ogni passo, l’algoritmo segue un percorso lungo il poligono dalla cima della pila al prossimo vertice che non è in una delle due tasche adiacenti alla cima della pila. Poi, mentre i primi due vertici della pila insieme a questo nuovo vertice non sono in posizione convessa, si apre la pila, prima di spingere finalmente il nuovo vertice sulla pila. Quando la traversata in senso orario raggiunge il punto di partenza, l’algoritmo restituisce la sequenza di vertici della pila come lo scafo.