Inviluppo convesso

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 insiemi 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 _{j}x_{j}$ , dove gli $x_{j}$ sono punti di $I$ e $\lambda _{j}$ sono numeri reali non negativi a somma 1, ovvero $\sum _{j=1}^{n}\lambda _{j}=1$ .

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

Unione di inviluppi convessi

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

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

Collegamenti esterni

(EN) Eric W. Weisstein, Inviluppo convesso, su MathWorld, Wolfram Research.
(EN) Inviluppo convesso, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

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

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

[1]