Apri il menu principale
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 insiemi 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 convessiModifica

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 computazionaleModifica

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

OsservazioniModifica

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

NoteModifica

  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.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica