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 è lui stesso.

In matematica si definisce inviluppo convesso (o talvolta involucro convesso) di un qualsiasi insieme $I$ l'intersezione di tutti gli insiemi convessi che contengono $I$.

Poiché l'intersezione di insieme 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.

Se l'insieme $I$ è sottoinsieme di uno spazio vettoriale reale, il suo 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_jx_j$, dove gli $x_j$ sono punti di $I$ e $\lambda_j$ sono numeri reali positivi a somma 1, ovvero $\sum_{j=1}^n \lambda_j=1$ .

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

Unione di inviluppi connessi

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 connesso; ogni volta che invece in $q_j$ c'è una "svolta a destra", sappiamo che questo punto non è un vertice dell'inviluppo connesso. 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.

Note

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica