Busta convessa

L' involucro convesso di un oggetto o di un raggruppamento di oggetti geometrici è l' insieme convesso più piccolo tra quelli che lo contengono.

In un piano, l'inviluppo convesso può essere paragonato alla regione delimitata da un elastico che racchiude tutti i punti che vengono rilasciati fino a quando non si contrae al massimo. L'idea sarebbe la stessa nello spazio con un palloncino che si sgonfia fino a quando non è a contatto con tutti i punti che si trovano sulla superficie dell'involucro convesso.

Definizione e proprietà di base

Supponiamo di trovarci in un contesto in cui la nozione di sottoinsieme convesso ha un significato (ad esempio in geometria affine su numeri reali), e indicheremo con E la cornice geometrica in cui ci collochiamo.

Definizione - O Una parte di E . La convessa busta di A è l' intersezione di tutte le parti convesse a E che contengono A .

Questa definizione ha senso, poiché c'è almeno una parte convessa di E che contiene A , vale a dire E stessa.

Da questa definizione e dal fatto che ogni intersezione di insiemi convessi è un insieme convesso, si deduce la seguente caratterizzazione dello scafo convesso.

Movimento - La convessa busta A è la più piccola parte convessa di E contenente A .

Sviluppato in modo più dettagliato, questo risultato caratterizza l'inviluppo convesso $Conv$ ( A ) come il sottoinsieme unico di E che soddisfa le seguenti tre condizioni:

$Conv$ ( A ) è convesso;
A è incluso in $Conv$ ( A );
se C è un sottoinsieme convesso di E contenente A , quindi $Conv$ ( A ) è incluso nel C .

Ad esempio, $Conv$ ( ∅ ) = ∅.

Descrizione in termini di baricentri

Nel resto di questa sezione, assumeremo che E sia uno spazio affine reale. Possiamo quindi affermare:

Proposta - La busta convessa A è l'insieme di combinazioni convesse (vale a dire, i centri di gravità di coefficienti non negativi) di famiglie di punti di A .

In altre parole: gli elementi dell'inviluppo convesso di A sono esattamente i punti $x$ di E che possiamo scrivere nella forma:

x = \ sum _ {{i = 1}} ^ {p} \ lambda _ {i} a_ {i}

, espressione in cui

p

è un numero intero, gli

a i

sono in A , i coefficienti

λ i

sono reali positivi e di somma

\ sum _ {{i = 1}} ^ {p} \ lambda _ {i} = 1.

Il caso della dimensione finita: un teorema di Carathéodory

L'affermazione di cui sopra può essere migliorata in dimensione finita, come notato da Constantine Carathéodory nel 1907 . Se indichiamo con n la dimensione di E , il teorema afferma che possiamo usare baricentri di punti p limitandoci al caso p = n + 1 per ricostituire l'intero inviluppo convesso. Così in un piano, dato A , costruiamo mentalmente il suo inviluppo convesso oscurando con il pensiero tutti i triangoli con vertici in A ; nella dimensione 3 useremmo tetraedri e così via.

Il teorema si afferma precisamente come segue:

Teorema - In uno spazio affine di dimensione n , il convesso busta un sottoinsieme A è un insieme di combinazioni convesse di famiglie di n + 1 punti di A .

Una volta che questa affermazione è nota, è facile dedurre un importante corollario:

Corollario - In uno spazio affine di dimensione finita, l'inviluppo convesso di un compatto è compatto.

(Considerando ad esempio nel spazio di Hilbert ℓ 2 , di base hilbertiano ( δ n ) n ∈ℕ , la sequenza (δ n / n ) n ∈ℕ e il suo limite 0 forma compatta , il cui inviluppo convesso n non è ancora chiusa . )

Aspetti algoritmici

In 2D

Il calcolo dell'inviluppo convesso di un insieme di punti è un classico problema della geometria computazionale. Sono stati inventati diversi algoritmi per risolvere questo problema, la loro complessità varia:

Jarvis camminare in , è il numero di punti di convesso; ${\ displaystyle O (nh)}$ $h$
L'algoritmo di Chan , in  ; ${\ displaystyle O (n \ log (h))}$
Corso Graham , in ; $O (n \ log (n))$
euristica di Akl-Toussaint ;
utilizzando il diagramma di Voronoi , in : i punti dell'involucro convesso definiscono cellule di Voronoi aperte, è sufficiente rilevare queste cellule e collegare i germi delle cellule adiacenti. $O (n \ log (n))$

Dimensioni dell'ordine superiori

Per un insieme finito di punti, lo scafo convesso è un poliedro convesso. Tuttavia, la sua rappresentazione non è così facile come nel caso del piano. Per dimensioni strettamente maggiori di 2, anche se si conoscono i bordi del poliedro, la costruzione delle sfaccettature non è un compito banale. Un certo numero di algoritmi è ancora noto per la dimensione 3, ma anche nel caso generale.

Riferimenti

Marcel Berger , Geometry [ dettaglio delle edizioni ], Prop. 11.1.8.4, volume 3, p. 26 nell'edizione del 1978.
(in) Charalambos D. Aliprantis e Kim C. Border , Infinite Analisi dimensionale: di un autostoppista guida , Springer ,2007( leggi in linea ) , p. 185.
(in) Michael Ian Shamos , Computational Geometry: PhD , Yale University ,1975
(en) Michael Ian Shamos e Dan Hoey , "Closest-point problems" , in Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science , Los Angeles, IEEE Computer Society Press,1975( leggi in linea ) , p. 151-162.

Vedi anche

Link esterno

(it) Algoritmi Convex Hull , applet Java 3D