Inviluppo convesso

Da Wikipedia, l'enciclopedia libera.

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$ .

Siccome l'intersezione di insieme convessi è a sua volta convessa, una definizione alternativa di inviluppo convesso è "il più piccolo ^[1] insieme convesso contenente $I$ ".

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 $λ 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.

[modifica] 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$ .

[modifica] Un approccio computazionale

Un interessante problema computazionale è, dato un insieme finito^[2] 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 $(ρ i,θ 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).

[modifica] Osservazioni

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

[modifica] Note

^ Ricordando la prima definizione, si intuisce che utilizzando la parola "piccolo" non sottointendiamo nessuna misura particolare, ma semplicemente l'ordinamento sugli insiemi definito da $A \le B \Leftrightarrow A \subset B$
^ In realtà possiamo benissimo immaginare che il dato di ingresso sia l'area racchiusa da una o più spezzate chiuse. In questo caso $p_1 \cdots p_n$ sono ovviamente i vertici della/e spezzata/e.