Inviluppo convesso

A sinistra: l'insieme blu non è convesso, l'insieme azzurro è il suo inviluppo convesso. A destra: l'insieme verde è convesso, quindi il suo inviluppo convesso è esso stesso.

In matematica si definisce inviluppo convesso (o talvolta involucro convesso) di un qualsiasi sottoinsieme $I$ di uno spazio vettoriale reale, l'intersezione di tutti gli insiemi convessi che contengono $I$.

Poiché l'intersezione di insiemi convessi è a sua volta convessa, una definizione alternativa di inviluppo convesso è "il più piccolo insieme convesso contenente $I$".

Intuitivamente, l'inviluppo convesso di un insieme di punti è la forma che assumerebbe un elastico allargato in modo da contenere tutti i punti e poi lasciato libero di restringersi: un poligono che ha alcuni di quei punti come vertici e li contiene tutti.

L'inviluppo convesso si può costruire come l'insieme di tutte le combinazioni convesse di punti di $I$, cioè tutti i punti del tipo $\sum _{j=1}^n{\lambda }_j{x}_j$, dove gli $x_j$ sono punti di $I$ e ${\lambda }_j$ sono numeri reali non negativi a somma 1, ovvero $\sum _{j=1}^n{\lambda }_j=1$ .

Evidentemente, se $I$ è convesso, il suo inviluppo convesso è $I$ stesso.

Unione di inviluppi convessi

Dati due insiemi $I,J$, se chiamiamo rispettivamente $C_I,C_J,C_{I\cup J}$ gli involucri convessi di $I,J,I\cup J$, è vera la seguente relazione: $C_I\cup C_J\subset C_{I\cup J}$.

Infatti abbiamo detto che se un insieme convesso contiene $I$, allora contiene anche $C_I$, e se contiene $J$ contiene anche $C_J$. Siccome $C_{I\cup J}$ è convesso e contiene sia $I$ che $J$ (perché contiene $I\cup J$), conterrà sia $C_I$ che $C_J$ (e quindi $C_I\cup C_J$).

Il viceversa in generale non è vero, ed un controesempio semplicissimo è il caso in cui $I$ e $J$ siano due punti distinti nel piano. Si osserva facilmente che un punto è per definizione convesso, e che quindi i loro inviluppi convessi sono $I$ e $J$ stessi. Ma l'inviluppo convesso di $I\cup J$ sarà un segmento, ossià conterrà strettamente $I\cup J=C_I\cup C_J$.

Un approccio computazionale

Un interessante problema computazionale è, dato un insieme finito di punti $I=p_1\cdots p_n$ nel piano, trovare $C_I$, l'inviluppo convesso di $I$. Sono stati trovati vari algoritmi che risolvono questo problema.

Uno dei più celebri è il cosiddetto Graham Scan: cerchiamo il punto più in basso (in caso di parità, quello più a sinistra tra quelli più in basso) e chiamiamolo $q_1$; siano ora $q_2\cdots q_n$ i rimanenti punti, ordinati in modo tale che $i>j\iff {\theta }_i>{\theta }_j$, dove $({\rho }_i,{\theta }_i)$ sono le coordinate polari di $q_i$. A questo punto scorriamo i punti $q_i$: ogni volta che in $q_i$ c'è una "svolta a sinistra" ma non in $q_{i-1}$, sappiamo che $q_i$ è un vertice dell'inviluppo convesso; ogni volta che invece in $q_j$ c'è una "svolta a destra", sappiamo che questo punto non è un vertice dell'inviluppo convesso. Questo algoritmo ha costo $O(n\log (n))$.

Un algoritmo efficiente per lo stesso problema è basato sulla ricorsione, sfruttando il caso base in cui $n=2$ (e l'inviluppo convesso di due punti è ovviamente il segmento che li congiunge) e creando in base a semplici regole l'inviluppo convesso di due insiemi convessi (passo ricorsivo).

Osservazioni

• L'inviluppo convesso è un concetto utile ad esempio in problemi di rilassamento.

Collegamenti esterni

• Template:Collegamenti esterni