Konvex boríték

A konvex burok egy tárgy vagy egy egyesülés geometriai objektumok a legkisebb konvex halmaz között azok, amelyek tartalmaznak azt.

Egy síkban a domború burkolat összehasonlítható azzal a régióval, amelyet egy gumiszalag határol, amely magában foglalja az összes felszabaduló pontot, amíg a maximálisan összehúzódik. Az ötlet ugyanaz lenne a térben egy léggömbbel, amely addig ereszkedne, amíg érintkezésbe nem kerül a domború burkolat felületén lévő összes ponttal.

Definíció és alapvető tulajdonságok

Feltételezzük, hogy olyan kontextusban vagyunk, ahol a konvex részhalmaz fogalmának jelentése van (például a valós számok affin geometriájában ), és E-vel jelöljük azt a geometriai keretet, amelybe magunkat helyezzük.

Definíció - Vagy egy részét E . A boríték konvex az A a kereszteződés minden fél konvex , hogy az E , amelyek tartalmaznak A .

Ez a meghatározás értelme, hiszen legalább egy domború részét E , amely egy , nevezetesen -E is.

Ebből a meghatározásból és abból a tényből, hogy a konvex halmazok bármely metszéspontja konvex halmaz, a konvex héj következő jellemzésére következtetünk.

Motion - A konvex boríték Egy van a legkisebb része konvex az E , amely tartalmaz egy .

Részletesebben kifejlesztve ez az eredmény a konvex burkolatot $Conv$ ( A ) jellemzi, mint E egyedi részhalmazát, amely kielégíti a következő három feltételt:

$Conv$ ( A ) konvex;
A szerepel a $Conv$ ( A ) $csoportban$ ;
ha C egy E konvex részhalmaz, amely A-t tartalmaz , akkor $Conv$ ( A ) szerepel a C-ben .

Például $Conv$ ( ∅ ) = ∅.

Leírás a barycenterek szempontjából

A szakasz további részében feltételezzük, hogy E egy igazi affin tér. Ezután kijelenthetjük:

Javaslat - A konvex burka egy halmaza konvex kombináció (azaz, a súlypontok , hogy nem-negatív együtthatók) családok pontok A .

Más szavakkal: az elemek a konvex burka egy pontosan pontok $x$ az E , hogy tudjuk írni a következő formában:

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

, olyan kifejezés, amelyben

p

egész szám, az

a i

értéke A , az

λ i

együtthatók pozitív valós értékek és összeg

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

A véges dimenzió esete: a Carathéodory tétele

A fenti állítás javítható véges dimenzióban, amint azt Konstantin Carathéodory a 1907 . Ha mi jelöljük n a dimenzió a E , a tétel kimondja, hogy tudjuk használni barycenters a p pont korlátozásával magunkat az esetben p = n + 1 rekonstruálni az egész konvex borítékot. Így egy síkban, adott A , mi mentálisan építésére domború borítékban sötétítéshez gondoltak összes háromszög csúcsok A ; a 3. dimenzióban tetraédereket használnánk stb.

A tétel pontosan a következőképpen van megfogalmazva:

Tétel - Egy affin tér dimenzió n , a konvex burok egy részhalmaza Egy egy sor konvex kombinációit családok a n + 1 pontok A .

Amint ez az állítás ismert, könnyen levezethető egy fontos következmény:

Következmény - A véges dimenziójú affin térben a kompakt domború burkája kompakt.

(Mivel például a Hilbert-tér ℓ 2 , a Hilbertian alapján ( δ n ) N ∈ℕ , a szekvencia (δ n / n ) n ∈ℕ és annak határát 0 formája egy kompakt , amelynek konvex boríték n nem is zárt . )

Algoritmikus szempontok

2D-ben

A ponthalmaz konvex burkolatának kiszámítása klasszikus probléma a számítási geometriában. Számos algoritmust találtak ki a probléma megoldására, összetettségük változó:

Jarvis séta az , hogy a pontok száma a konvex burok; ${\ displaystyle O (nh)}$ $h$
Chan algoritmusa , in  ; ${\ displaystyle O (n \ log (h))}$
Graham tanfolyam , in ; $O (n \ log (n))$
heurisztikus Akl-Toussaint ;
a Voronoi diagram segítségével : in : a konvex burok pontjai meghatározzák a nyitott Voronoi sejteket, elegendő ezeket a sejteket detektálni és összekapcsolni a szomszédos sejtek csíráit. $O (n \ log (n))$

Magasabb rendelési méretek

Véges ponthalmaz esetén a domború test egy domború poliéder . Ábrázolása azonban nem olyan egyszerű, mint a terv esetében. Szigorúan 2-nél nagyobb méretek esetén, még akkor is, ha a poliéder szélei ismertek, a fazetták felépítése nem triviális feladat. Bizonyos számú algoritmus még ismert a 3. dimenzióhoz, de általános esetben is.

Hivatkozások

Marcel Berger , geometria [ a kiadások részlete ], Prop. 11.1.8.4, 3. kötet, p. 26 az 1978-as kiadásban.
(a) Charalambos D. Aliprantis és Kim C. Border , végtelen dimenziós Elemzés: A stoppos útmutató , Springer ,2007( online olvasható ) , p. 185.
(in) Michael Ian Shamos , Computational Geometry: PhD , Yale University ,1975
en) Michael Ian Shamos és Dan Hoey , „Legközelebbi problémák” , a 16. éves IEEE szimpózium folytatásaként a számítástechnika alapjairól , Los Angeles, IEEE Computer Society Press,1975( online olvasható ) , p. 151-162.

Lásd is

Kapcsolódó cikkek

Külső hivatkozás

(en) Konvex Hull algoritmusok , 3D Java kisalkalmazás