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

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

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

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 , cioè tutti i punti del tipo , dove gli sono punti di e sono numeri reali positivi a somma 1, ovvero .

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

Unione di inviluppi connessi[modifica | modifica wikitesto]

Dati due insiemi , se chiamiamo rispettivamente gli involucri convessi di , è vera la seguente relazione: .

Infatti abbiamo detto che se un insieme convesso contiene , allora contiene anche , e se contiene contiene anche . Siccome è convesso e contiene sia che (perché contiene ), conterrà sia che (e quindi, ovviamente, ).

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

Un approccio computazionale[modifica | modifica wikitesto]

Un interessante problema computazionale è, dato un insieme finito[1] di punti nel piano, trovare , l'inviluppo convesso di . 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 ; siano ora i rimanenti punti, ordinati in modo tale che , dove sono le coordinate polari di . A questo punto scorriamo i punti : ogni volta che in c'è una "svolta a sinistra" ma non in , sappiamo che è un vertice dell'inviluppo connesso; ogni volta che invece in c'è una "svolta a destra", sappiamo che questo punto non è un vertice dell'inviluppo connesso. Questo algoritmo ha costo .

Un algoritmo efficiente per lo stesso problema è basato sulla ricorsione, sfruttando il caso base in cui (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[modifica | modifica wikitesto]

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

Note[modifica | modifica wikitesto]

  1. ^ In realtà possiamo benissimo immaginare che il dato di ingresso sia l'area racchiusa da una o più spezzate chiuse. In questo caso sono ovviamente i vertici della/e spezzata/e.
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica