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.
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:
Például Conv ( ∅ ) = ∅.
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:
, 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 összegA 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 . )
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ó:
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.
(en) Konvex Hull algoritmusok , 3D Java kisalkalmazás
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">