Konveks konvolut

Den konvekse konvolut af et objekt eller en gruppe geometriske objekter er det mindste konvekse sæt blandt dem, der indeholder det.

I et plan kan den konvekse konvolut sammenlignes med det område, der er afgrænset af et gummibånd, der omfatter alle de punkter, der frigøres, indtil det kontraherer maksimalt. Ideen ville være den samme i rummet med en ballon, der ville tømme, indtil den var i kontakt med alle de punkter, der er på overfladen af den konvekse konvolut.

Definition og grundlæggende egenskaber

Vi antager at være i en sammenhæng, hvor begrebet konveks delmængde har en betydning (for eksempel i affin geometri på reelle tal), og vi betegner med E den geometriske ramme, hvor vi placerer os.

Definition - Enten En del af E . Den kuvert konvekse af A er skæringspunktet for alle parter konveks til E , som indeholder A .

Denne definition giver mening, da der er mindst en konveks del af E, som indeholder A , nemlig E selv.

Fra denne definition og fra det faktum, at ethvert skæringspunkt for konvekse sæt er et konveks sæt, udleder vi følgende karakterisering af det konvekse skrog.

Bevægelse - Den konvekse hylster A er den mindste del konvekse af E , som indeholder A .

Udviklet mere detaljeret karakteriserer dette resultat den konvekse konvolut $Conv$ ( A ) som den unikke delmængde af E, der opfylder følgende tre betingelser:

$Konv$ ( A ) er konveks;
A er inkluderet i $Conv$ ( A );
hvis C er en konveks delmængde af E indeholdende A , derefter $Conv$ ( A er) indbefattet i C .

For eksempel er $Conv$ ( ∅ ) = ∅.

Beskrivelse med hensyn til barycenters

I resten af dette afsnit antager vi, at E er et reelt affinalt rum. Vi kan derefter angive:

Forslag - Den konvekse hylster af A er det sæt af konvekse kombinationer (det vil sige, de tyngdepunkter til ikke-negative koefficienter) af familier af punkter i A .

Med andre ord: elementerne i den konvekse konvolut af A er nøjagtigt de punkter $x$ af E, som vi kan skrive i form:

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

, udtryk, hvor

p

er et heltal,

a i

er i A , koefficienterne

λ i

er positive reelle og af sum

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

Sagen om begrænset dimension: en sætning af Carathéodory

Ovenstående udsagn kan forbedres i begrænset dimension, som konstateret af Constantine Carathéodory i 1907 . Hvis vi betegne som n den dimension af E , sætningen angiver, at vi kan bruge barycenters af p point ved at begrænse os til tilfældet p = n til + 1 rekonstituere hele konvekse kuvert. Således i et plan, givet A , konstruerer vi mentalt dens konvekse kuvert ved mørkere ved tanke alle trekanter med hjørner i A ; i dimension 3 ville vi bruge tetraeder osv.

Teoremet angives nøjagtigt som følger:

Teorem - I en affin rum af dimension n , den konvekse konvolutten en delmængde A er et sæt af konvekse kombinationer af familier af n + 1 punkter A .

Når denne erklæring er kendt, er det let at udlede en vigtig følge:

Corollary - I et affinalt rum med en begrænset dimension er den kompakte konvolut af en kompakt kompakt.

(Mens der fx i Hilbert-rummet ℓ 2 , på Hilbertian-basis ( δ n ) n ∈ℕ , dannes sekvensen (δ n / n ) n ∈ℕ og dens grænse 0 en kompakt , hvis konvekse kuvert n ikke engang er lukket . )

Algoritmiske aspekter

I 2D

Den beregning af den konvekse hylster af et sæt af punkter er et klassisk problem i beregningsmæssige geometri. Flere algoritmer er opfundet for at løse dette problem, deres kompleksitet varierer:

Jarvis går ind , idet det er antallet af punkter i det konvekse skrog; ${\ displaystyle O (nh)}$ $h$
Chans algoritme , i  ; ${\ displaystyle O (n \ log (h))}$
Graham kursus , i ; $O (n \ log (n))$
heuristisk over Akl-Toussaint ;
ved hjælp af Voronoi-diagrammet , i : punkterne i den konvekse kuvert definerer åbne Voronoi-celler, er det nok at detektere disse celler og forbinde bakterierne i de tilstødende celler. $O (n \ log (n))$

Højere ordredimensioner

For et endeligt sæt punkter er det konvekse skrog en konveks polyhedron . Imidlertid er dets repræsentation ikke så let som i planens tilfælde. For dimensioner, der er strengt større end 2, er det ikke en triviel opgave , selvom polyhedronens kanter er kendt. Et vist antal algoritmer er stadig kendt for dimension 3, men også i det generelle tilfælde.

Referencer

Marcel Berger , Geometry [ detalje af udgaver ], Rekvisit. 11.1.8.4, bind 3, s. 26 i 1978-udgaven.
(i) Charalambos D. Aliprantis og Kim C. Border , Infinite Dimensional Analysis: A Hitchhiker Guide , Springer ,2007( læs online ) , s. 185.
(i) Michael Ian Shamos , Computational Geometry: Ph.d. , Yale University ,1975
(en) Michael Ian Shamos og Dan Hoey , "Closest-point problems" , i processen med 16. årlige IEEE Symposium on Foundations of Computer Science , Los Angeles, IEEE Computer Society Press,1975( læs online ) , s. 151-162.

Se også

Relaterede artikler

Eksternt link

(da) Konvekse skrogalgoritmer , 3D Java-applet