Negli algoritmi geometrici , il calcolo dell'inviluppo convesso è un problema algoritmico . Consiste, dato un insieme di punti, nel calcolare il loro inviluppo convesso .
Lo scafo convesso di un insieme di punti è il più piccolo insieme convesso che li contiene tutti. È un poliedro i cui vertici sono punti dell'insieme. Il calcolo dell'inviluppo convesso consiste nel calcolare una rappresentazione compatta dell'inviluppo, il più delle volte i suoi vertici.
Questo è un problema che ha molte applicazioni, ad esempio nel riconoscimento di modelli, e che è centrale per la geometria computazionale .
Il caso planare è il caso in cui i punti sono disposti nel piano. Misuriamo la complessità nel tempo in funzione del numero di punti dell'input n , e del numero di punti sull'inviluppo h . Ci sono molti algoritmi per questo caso.
L'idea della passeggiata Jarvis (o algoritmo di confezione regalo ) è di "avvolgere" l'insieme di punti in una "carta da regalo": appendiamo questa carta in uno dei punti, la stendiamo, quindi giriamo intorno al punto nube. La complessità dell'algoritmo è O (nh) .
Il corso Graham (noto anche come scansione di Graham ) è trovare il punto dell'asse x più piccolo, ordinare tutti gli altri punti dall'angolo che fanno con esso (e l'asse x), quindi considerare le terzine di punti successivi, per determinare quali sono nella busta. La sua complessità è quella di selezione , vale a dire O (n.log (n)) .
L' algoritmo Chan , procede per fasi. Prima un partizionamento dei punti in più gruppi, poi il calcolo degli inviluppi convessi di questi gruppi con un algoritmo in O (n.log (n)) (come il Graham walk ), e infine un Jarvis walk utilizzando questi inviluppi già calcolati . La sua complessità è in O (n.log (h)) .
Quickhull è un algoritmo divide et impera . La sua complessità media è O (n.log (n)). La sua complessità nel caso peggiore è O (n²).
L' algoritmo di Shamos è un algoritmo divide et impera. La sua complessità è O (n.log (n)).
L' algoritmo di Kirkpatrick e Seidel (in) ha una complessità di O (n.log (h)) .
Esistono altri algoritmi, come l'algoritmo di Andrew.
L' algoritmo Preparata-Hong funziona per le dimensioni 2 e 3.
Per dimensioni maggiori di 2, l'algoritmo quickhull e l'algoritmo di Chan funzionano.
Esistono anche algoritmi per approssimare l'inviluppo convesso.