Inviluppo convesso

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

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.

Poiché l'intersezione di insiemi convessi è a sua volta convessa, una definizione alternativa di inviluppo convesso è "il più piccolo insieme convesso contenente ${\displaystyle 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 ${\displaystyle I}$, cioè tutti i punti del tipo ${\displaystyle \sum _{j=1}^{n}\lambda _{j}x_{j}}$, dove gli ${\displaystyle x_{j}}$ sono punti di ${\displaystyle I}$ e ${\displaystyle \lambda _{j}}$ sono numeri reali non negativi a somma 1, ovvero ${\displaystyle \sum _{j=1}^{n}\lambda _{j}=1}$ .

Evidentemente, se ${\displaystyle I}$ è convesso, il suo inviluppo convesso è ${\displaystyle I}$ stesso.

Unione di inviluppi convessi

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

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

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

Un approccio computazionale

Un interessante problema computazionale è, dato un insieme finito^[1] di punti ${\displaystyle I={p_{1}\cdots p_{n}}}$ nel piano, trovare ${\displaystyle C_{I}}$, l'inviluppo convesso di ${\displaystyle 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 ${\displaystyle q_{1}}$; siano ora ${\displaystyle q_{2}\cdots q_{n}}$ i rimanenti punti, ordinati in modo tale che ${\displaystyle i>j\Leftrightarrow \theta _{i}>\theta _{j}}$, dove ${\displaystyle (\rho _{i},\theta _{i})}$ sono le coordinate polari di ${\displaystyle q_{i}}$. A questo punto scorriamo i punti ${\displaystyle q_{i}}$: ogni volta che in ${\displaystyle q_{i}}$ c'è una "svolta a sinistra" ma non in ${\displaystyle q_{i-1}}$, sappiamo che ${\displaystyle q_{i}}$ è un vertice dell'inviluppo convesso; ogni volta che invece in ${\displaystyle q_{j}}$ c'è una "svolta a destra", sappiamo che questo punto non è un vertice dell'inviluppo convesso. Questo algoritmo ha costo ${\displaystyle O(n\,\log(n))}$.

Un algoritmo efficiente per lo stesso problema è basato sulla ricorsione, sfruttando il caso base in cui ${\displaystyle 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.