Inviluppo convesso
# Inviluppo convesso

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, ovviamente, $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\Leftrightarrow \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.
