Főmenü megnyitása
A pirossal jelölt halmaz konvex burka a kék és piros konvex halmaz.

A matematikában az euklideszi sík vagy euklideszi tér (vagy általánosabban, egy valós számok fölötti affin tér) X ponthalmazának konvex burka vagy konvex burkolója az a legkisebb konvex halmaz, ami X-et tartalmazza. Ha X a sík korlátos halmaza, a konvex burok elképzelhető úgy is, mintha X köré gumiszalagot feszítenénk.[1]

Formálisan a konvex burok definiálható úgy is, mint az X-et tartalmazó összes konvex halmaz metszete, vagy az X pontjai összes konvex kombinációjának halmaza. Ez utóbbi definíció segítségével a konvex burok definíciója kiterjeszthető az euklideszi terekről tetszőleges valós vektorterekre; ez pedig tovább általánosítható irányított matroidokra.[2]

A síkban vagy más, alacsony dimenziójú euklideszi terekben elhelyezkedő véges ponthalmaz konvex burka előállításának algoritmikus problémája a számítási geometria alapvető problémáinak egyike.

Tartalomjegyzék

DefiníciókSzerkesztés

 
Néhány pont konvex burka a síkban
 
Véges halmaz konvex burka: a gumiszalag-analógia

Egy ponthalmaz definíció szerint akkor konvex, ha bármely két pontját összekötő egyenes szakasz pontjait is tartalmazza. Ekkor adott X halmaz konvex burka a következő módokon definiálható:

  1. Az (egyedi) minimális, X-et tartalmazó konvex halmaz
  2. Az X-et tartalmazó összes konvex halmaz metszete
  3. Az X pontjai összes konvex kombinációinak halmaza
  4. Az összes, X-ben található csúcsokkal rendelkező szimplex uniója.

Az első definícióról nem nyilvánvaló, hogy működhet: miért lenne biztos, hogy minden X-re létezik az X-et tartalmazó egyedi, minimális konvex halmaz? A második meghatározás, miszerint az X-et tartalmazó összes konvex halmaz metszete, már jól definiált, és minden más, X-et tartalmazó Y halmaz részhalmaza, hiszen X a metszésbe hozott halmazok között szerepel. Tehát éppen egyedi minimális konvex halmaz, ami X-et tartalmazza. Minden, X-et tartalmazó konvex halmaznak (a konvexitás miatt) tartalmaznia kell X pontjainak összes konvex kombinációját, tehát az összes konvex kombináció halmaza részhalmaza az összes X-et tartalmazó konvex halmaz metszetének. Megfordítva, az összes konvex kombináció halmaza önmaga is az X-et tartalmazó konvex halmaz, tehát szintén tartalmazza az összes X-et tartalmazó konvex halmaz metszetét, tehát a két definíció által meghatározott halmazok azonosak. Valójában, Caratheodory tétele szerint, ha X egy N dimenziós vektortér részhalmaza, a fenti definícióban mindössze N + 1 pont konvex kombinációjára van szükség. Tehát a síkban a három vagy több pont alkotta X halmaz konvex burka megegyezik az X ponthármasai által meghatározott összes háromszög uniójával, általánosabban pedig az N dimenziós térben a konvex burok megegyezik a legalább N + 1 pontból álló X pont-N-esei által meghatározott szimplexek uniójával.

Ha X konvex burka zárt halmaz (ami például akkor következik be, ha X véges halmaz, vagy általánosabban, egy kompakt halmaz), akkor az megegyezik az összes, X-et tartalmazó zárt féltér metszetével. A hipersík-szeparációs tétel szerint ebben az esetben a konvex burkon kívül eső bármely pont a konvex buroktól alkalmasan megválasztott féltérrel elválasztható. Léteznek azonban olyan konvex halmazok, illetve ezek burkai, melyek nem reprezentálhatók ilyen módon – például a nyílt félterek is ilyenek.

Elvontabban, a Conv() konvex burok-művelet a lezárási operátor jellemző tulajdonságaival rendelkezik:

  • Extenzív, ami azt jelenti, hogy bármely X konvex burka az X bővebb halmaza.
  • nem csökkenő, tehát bármely X és Y halmazra, ahol X ⊆ Y, az X konvex burka is részhalmaza Y konvex burkának.
  • Idempotens, tehát bármely X halmaz konvex burka megegyezik az X halmaz konvex burkának konvex burkával.

Véges ponthalmaz konvex burkaSzerkesztés

 
Felső és alsó burok

Egy véges   ponthalmaz konvex burka megegyezik pontjai lehetséges konvex kombinációinak halmazával. Egy konvex kombinációban minden  -beli   ponthoz egy   súlyt vagy együtthatót rendelnek olyan módon, hogy a súlyok nem negatívak, összegük pedig éppen egy. A súlyok segítségével kiszámítható a pontok súlyozott átlaga. Bárhogyan választják meg az együtthatókat, a létrejött konvex kombináció a konvex burok egy pontját adja, a teljes konvex burok pedig létrejön, ha az összes lehetséges konvex kombináció megalkotásával. Egyetlen képletben kifejezve, a konvex burok a következő halmazzal egyezik meg:

 

Az   véges ponthalmaz konvex burka az n = 2 esetben konvex sokszög, általánosabban az  -t tekintve konvex politóp. Az   minden   pontja, ami nincs benne a többi pont konvex burkában (tehát:  ) a   egy csúcsa. Valóban, minden  -beli konvex politóp megegyezik a csúcsok konvex burkával.

Ha   pontjai mind egy egyenesre esnek, a konvex burok a legszélső két pontot összekötő egyenes szakasszal egyezik meg. Ha az   a sík nem üres, véges részhalmaza, képzeletben kifeszíthetünk egy gumiszalagot úgy, hogy körbevegye a teljes  -t, majd elengedjük, hogy összehúzódhasson; mikor feszes lesz, éppen az   konvex burkát foglalja magába.[1]

Két dimenzióban a konvex burkot néha két töröttvonalra bontják, a felső és az alsó burokra, melyek a burok legbaloldalibb, illetve legjobboldalibb pontjai között feszülnek. Általánosabban, tetszőleges dimenzióban elhelyezkedő általános helyzetű pontok esetében a konvex burok minden eggyel alacsonyabb dimenziós „lapja” vagy fölfelé (elválasztva a burkot a fölötte lévő pontoktól), vagy lefelé mutat; a fölfelé mutató lapok uniója egy topologikus korongot alkot, ami a felső burok; hasonlóan, a lefelé mutató lapok uniója alkotja az alsó burkot.[3]

Konvex burok kiszámításaSzerkesztés

 
Egy ponthalmaz konvex burkának iteratív kiszámítása egy szimplexből kiindulva.

A számítási geometria területén több algoritmus ismert véges ponthalmazok és más mértani objektumok konvex burkának kiszámítására.

A konvex burok meghatározása a kívánt konvex alakot leíró egyértelmű, hatékony adatstruktúra előállítását jelenti. A megfelelő algoritmusok bonyolultságát általában a bemeneti pontok, n, illetve a konvex burok pontjai, h függvényében adják meg.

Két, illetve három dimenzióban több olyan kimenetérzékeny algoritmus ismert, ami a konvex burkot O(n log h) időben meghatározza. Háromnál magasabb d dimenziókban a konvex burok kiszámításához az eddig ismert algoritmusoknak   időre van szükség, ami éppen a kimenetérzékeny algoritmus bonyolultsága a legrosszabb esetben.[4]

Minkowski-összeg és konvex burkokSzerkesztés

 
Halmazok Minkowski-összege. A Q1=[0,1]2 és Q2=[1,2]2 négyzetek összege a Q1+Q2=[1,3]2 négyzet.

A konvex burok képzésének művelete „jól viselkedik” a halmazok Minkowski-összeadását tekintve.

  • Valós vektortérben a két (nem üres) 1 és S2 halmaz Minkowski-összege definíció szerint az S1 + S2, az összegzendők vektorainak elemenkénti összegzésével képezett összeg:
S1 + S2 = { x1 + x2 : x1 ∈ S1 és x2 ∈ S2 }.

Általánosabban, az Sn véges (nem üres) halmazcsalád Minkowski-összege definíció szerint az összegzendők vektorainak elemenkénti összegzésével képezett összeg:

∑ Sn = { ∑ xn : xn ∈ Sn }.
  • Egy valós vektortér minden S1 és S2 részhalmazára igaz, hogy Minkowski-összegük konvex burka megegyezik konvex burkaik Minkowski-összegével:
Conv( S1 + S2 ) = Conv( S1 ) + Conv( S2 ).

Ez általánosabban bármennyi véges, nem üres halmazra is kimondható:

Conv(  ∑ Sn  ) = ∑ Conv( Sn ).

Más szavakkal, a Minkowski-összegzés és a konvex burok képzése kommutatív műveletek.[5][6]

A fentiekből látszik, hogy a Minkowski-összeadás jelentősen különbözik a halmazelmélet unió műveletétől; és valóban, két konvex halmaz uniója nem feltétlenül konvex: általános esetben a Conv(S) ∪ Conv(T) ⊆ Conv(S ∪ T) valódi részhalmazt és nem egyenlőséget jelent. A konvex burok művelet kell ahhoz, hogy a konvex halmazok halmaza teljes hálót alkosson, melynek az unió (egyesítés) művelete a konvex halmazok uniójának konvex burkával egyezik meg:

Conv(S) ∨ Conv(T) = Conv( S ∪ T ) = Conv( Conv(S) ∪ Conv(T) ).

Más struktúrákkal való kapcsolataSzerkesztés

 
Egy 120 pontból álló felhő 3D-s konvex burka

Egy ponthalmaz Delaunay-háromszögelése és annak duálisa, a Voronoj-cella matematikailag a konvex burkok rokonainak tekinthetők: egy Rn-beli ponthalmaz Delaunay-háromszögelése tekinthető úgy is, mint egy Rn+1-beli konvex burok projekciója.[7]

Topologikusan tekintve, egy nyílt halmaz konvex burka mindig nyílt, egy kompakt halmazé pedig mindig kompakt; léteznek azonban olyan tárt halmazok, melyek konvex burka nem zárt.<ref(Grünbaum 2003), p. 16.</ref> Például a

 

zárt halmaz konvex burka a nyitott felső félsík.

AlkalmazásaiSzerkesztés

A konvex burok előállításának számos gyakorlati alkalmazása van az alakfelismerés, képfeldolgozás, a statisztika, földrajzi információs rendszerek, a játékelmélet, fázisdiagramok előállítása, az absztrakt interpretáció-alapú statikus kódanalízis területén. Eszközként, építőelemként is szolgál más számítási geometriai algoritmusok részeként, ilyen például a ponthalmaz szélességét és átmérőjét megállapító forgó tolómérce módszer.

A konvex burok fogalma az etológiában minimális konvex sokszög (MCP) néven ismert, ami egy állat mozgáskörzetének klasszikus, bár leegyszerűsítő megközelítése azon pontok alapján, ahol az állatot megfigyelték.[8] A kiugró értékek az MCP-t rendkívül megnövelhetik, ezért szokás olyan megközelítést alkalmazni, hogy csak a megfigyelések egy részét veszik bele az MCP-be (például úgy, hogy az a pontok 95%-át tartalmazza).[9]

Kapcsolódó szócikkekSzerkesztés

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Convex hull című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

JegyzetekSzerkesztés

  1. a b (de Berg et al. 2000), p. 3.
  2. Knuth (1992).
  3. (de Berg et al. 2000), p. 6. A burok két töröttvonalra való felbontásának ötlete a Graham-pásztázás egy hatékony variánsából származik, amit (Andrew 1979) fejlesztett ki.
  4. Chazelle (1993).
  5. (Krein & Šmulian 1940), Theorem 3, pages 562–563.
  6. A Minkowski-összegképzés és a konvexifikáció felcserélhetőségét (Schneider 1993)-ban a Theorem 1.1.2 taglalja (2–3. oldal); ez a mű a Minkowski-összeghalmazok konvex burka terén született addigi eredmények nagy részét tárgyalja, a következő helyen: "Chapter 3 Minkowski addition" (126–196. oldal).
  7. Brown (1979).
  8. (Kernohan, Gitzen & Millspaugh 2001), p. 137–140
  9. Példák: a v.adehabitat.mcp GRASS modul és az adehabitatHR R csomag százalékos paraméterekkel az MCP-számításhoz.

További információkSzerkesztés

A meghatározatlan nyelvű +/- Wikikönyvekben
további információk találhatók