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 I di uno spazio vettoriale reale 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.

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_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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Un interessante problema computazionale è, dato un insieme finito[1] 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[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 p_1 \cdots p_n sono ovviamente i vertici della/e spezzata/e.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica