Vizsgáljuk meg azt az általános esetet, amikor az algoritmus bemenete egy véges, rendezetlen ponthalmaz a kartéziánus síkon. Egy fontos speciális esetet, amikor a pontok egy egyszerű sokszög határán való áthaladás sorrendjében adottak, később egy külön alfejezetben ismertetünk.
Ha nem minden pont van ugyanazon az egyenesen, akkor a konvex héjuk egy konvex sokszög, amelynek csúcsai a bemeneti halmaz néhány pontja. Leggyakoribb ábrázolása a csúcsainak a határa mentén az óramutató járásával megegyező vagy ellentétes irányba rendezett listája. Bizonyos alkalmazásokban kényelmes egy konvex sokszöget félsíkok halmazának metszeteként ábrázolni.
A számítási bonyolultság alsó korlátjaSzerkesztés
A síkban lévő pontok véges halmaza esetén a konvex sokszögként ábrázolt konvex héj megtalálásának számítási bonyolultságára vonatkozó alsó korlát a következő redukcióval könnyen megmutatható, hogy ugyanaz, mint a rendezés esetében. Az x 1 , … , x n halmazra {\displaystyle x_{1},\dots ,x_{n}}
számok rendezéséhez tekintsük a pontok ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})} halmazát.
pontok a síkban. Mivel ezek egy parabolán fekszenek, ami egy konvex görbe, könnyen belátható, hogy a konvex burkolat csúcsai a határ mentén haladva az x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}} számok rendezett sorrendjét adják.
. Nyilvánvalóan lineáris időre van szükség a számok pontokká történő leírt átalakításához, majd rendezett sorrendjük kivonásához. Ezért általános esetben az n pontok konvex burkát nem lehet gyorsabban kiszámítani, mint a rendezést.
A rendezésre vonatkozó szabványos Ω(n log n) alsó korlát a számítás döntési fa modelljében bizonyított, amelyben csak numerikus összehasonlítások végezhetők, de aritmetikai műveletek nem; ebben a modellben azonban a konvex héjakat egyáltalán nem lehet kiszámítani. A rendezés Ω(n log n) időt igényel a számítás algebrai döntési fa modelljében is, amely modell alkalmasabb a konvex héjakra, és ebben a modellben a konvex héjak is Ω(n log n) időt igényelnek. A számítógépes aritmetika olyan modelljeiben azonban, amelyek lehetővé teszik a számok O(n log n) időnél gyorsabb rendezését, például egészszámos rendezési algoritmusok alkalmazásával, a síkbeli konvex burkok is gyorsabban kiszámíthatók: a konvex burkok Graham-féle szkennelési algoritmusa egyetlen rendezési lépésből áll, amelyet lineáris mennyiségű további munka követ.
Optimális kimenet-érzékeny algoritmusokSzerkesztés
A fentiek szerint a konvex héj megtalálásának bonyolultsága az n bemeneti méret függvényében Ω(n log n) alsó korlátos. Néhány konvex héj algoritmus bonyolultsága azonban jellemezhető mind az n bemeneti méret, mind a h kimeneti méret (a héjban lévő pontok száma) szempontjából. Az ilyen algoritmusokat kimenet-érzékeny algoritmusoknak nevezzük. Ezek aszimptotikusan hatékonyabbak lehetnek a Θ(n log n) algoritmusoknál olyan esetekben, amikor h = o(n).
A kimenet-érzékeny konvex héj algoritmusok legrosszabb esetre vonatkozó futási idejének alsó korlátja Ω(n log h) volt sík esetben. Több olyan algoritmus is létezik, amely eléri ezt az optimális időbonyolultságot. A legkorábbiat Kirkpatrick és Seidel mutatta be 1986-ban (akik “a végső konvex héj algoritmusnak” nevezték). Egy sokkal egyszerűbb algoritmust Chan fejlesztett ki 1996-ban, és Chan algoritmusának nevezik.
AlgoritmusokSzerkesztés
Az ismert konvex héj algoritmusok az alábbiakban az első publikáció dátuma szerint vannak felsorolva. Az egyes algoritmusok időbonyolultságát az n bemeneti pontok száma és a burkon lévő pontok száma h. Megjegyzendő, hogy a legrosszabb esetben h ugyanolyan nagy lehet, mint n.
- Ajándékcsomagolás, más néven Jarvis menet – O(nh)
A legegyszerűbb (bár a legrosszabb esetben nem a legidőhatékonyabb) síkbeli algoritmusok egyike. Chand & Kapur 1970-ben és R. A. Jarvis 1973-ban egymástól függetlenül alkotta meg. O(nh) időbonyolultságú, ahol n a halmaz pontjainak száma, h pedig a hajótest pontjainak száma. A legrosszabb esetben a komplexitás Θ(n2). - Graham scan – O(n log n)
Egy kicsit bonyolultabb, de sokkal hatékonyabb algoritmus, amelyet Ronald Graham publikált 1972-ben. Ha a pontok már valamelyik koordináta vagy egy fix vektorhoz viszonyított szög szerint vannak rendezve, akkor az algoritmus O(n) időt vesz igénybe. - Quickhull
Elkészítette egymástól függetlenül 1977-ben W. Eddy és 1978-ban A. Bykat. A quicksort algoritmushoz hasonlóan a várható időbonyolultsága O(n log n), de legrosszabb esetben O(n2)-re degenerálódhat. - Oszd meg és uralkodj – O(n log n)
Egy másik O(n log n) algoritmus, 1977-ben publikálta Preparata és Hong. Ez az algoritmus háromdimenziós esetre is alkalmazható. - Monoton lánc, más néven Andrew algoritmusa – O(n log n)
1979-ben publikálta A. M. Andrew. Az algoritmus a Graham-szkennelés egy változatának tekinthető, amely a pontokat lexikográfiailag rendezi a koordinátáik alapján. Ha a bemenet már rendezett, akkor az algoritmus O(n) időt vesz igénybe. - Inkrementális konvex héj algoritmus – O(n log n)
1984-ben publikálta Michael Kallay. - Kirkpatrick-Seidel algoritmus – O(n log h)
Az első optimális kimenet-érzékeny algoritmus. Az oszd meg és uralkodj algoritmust módosítja a házasság-előtti-hódítás technikájának és az alacsony dimenziós lineáris programozásnak a felhasználásával. Kirkpatrick és Seidel publikálta 1986-ban. - Chan algoritmusa – O(n log h)
Egy egyszerűbb, optimális kimenet-érzékeny algoritmus, amelyet Chan 1996-ban készített. Az ajándékcsomagolást kombinálja egy O(n log n) algoritmus (például a Graham-szkennelés) végrehajtásával a bemenet kis részhalmazain.
Akl-Toussaint heurisztikaSzerkesztés
A következő egyszerű heurisztikát gyakran használják első lépésként a konvex héj algoritmusok implementációiban a teljesítményük javítása érdekében. Ez Selim Akl és G. T. Toussaint 1978-as hatékony konvex héj algoritmusán alapul. A módszer lényege, hogy gyorsan kizárunk sok olyan pontot, amely egyébként sem lenne része a konvex burkolatnak. Ez a módszer a következő elgondoláson alapul. Keressük meg a két legalacsonyabb és legmagasabb x-koordinátájú pontot, valamint a két legalacsonyabb és legmagasabb y-koordinátájú pontot. (Mindegyik művelet O(n) értéket vesz igénybe). Ez a négy pont egy konvex négyszöget alkot, és minden olyan pont, amely ebben a négyszögben fekszik (kivéve az eredetileg kiválasztott négy csúcsot), nem része a konvex héjnak. Az összes olyan pont megtalálása, amely ebben a négyszögben fekszik, szintén O(n), és így az egész művelet O(n). Opcionálisan az x- és y-koordináták legkisebb és legnagyobb összegével, valamint az x- és y-koordináták legkisebb és legnagyobb különbségével rendelkező pontok is hozzáadhatók a négyszöghöz, így egy szabálytalan konvex nyolcszöget alkotva, amelynek belsejét nyugodtan el lehet dobni. Ha a pontok véletlen változók, akkor a valószínűségi sűrűségfüggvények egy szűk, de gyakran előforduló osztálya esetében ez az eldobható előfeldolgozási lépés a konvex héj algoritmust lineáris várható idő alatt futtathatóvá teszi, még akkor is, ha a konvex héj algoritmus legrosszabb esetben a komplexitása n-ben négyzetes.
On-line és dinamikus konvex héj problémák Szerkesztés
A fenti tárgyalás azt az esetet veszi figyelembe, amikor minden bemeneti pont előre ismert. Két másik beállítást is figyelembe vehetünk.
- Online konvex héj probléma: A bemeneti pontokat egymás után, egymás után kapjuk meg. Miután minden egyes pont megérkezett a bemenetre, hatékonyan kell kiszámítani az eddig kapott ponthalmaz konvex burkát.
- Dinamikus konvex burkolat karbantartás: A bemeneti pontok szekvenciálisan beszúrhatók vagy törölhetők, és a konvex burkot minden egyes beszúrási/törlési művelet után frissíteni kell.
Egy pont beszúrása legfeljebb 1-gyel növelheti a konvex burkolat csúcsainak számát, míg a törlés egy n csúcsú konvex burkot n-1 csúcsúvá alakíthat.
Az online változatot pontonként O(log n)-rel lehet kezelni, ami aszimptotikusan optimális. A dinamikus változat műveletenként O(log2 n)-el kezelhető.
Egyszerű sokszögEdit
Egy egyszerű sokszög konvex burkolatát a sokszög darabokra osztja, amelyek közül az egyik maga a sokszög, a többi pedig a sokszög határának egy darabja és egyetlen burkolati él által határolt zseb. Bár számos algoritmust publikáltak az egyszerű sokszög konvex burkának megkonstruálására, ezek közel fele hibás, McCallum és Avis adta meg az első helyes algoritmust, Graham & Yao (1983) és Lee (1983) későbbi egyszerűsítése csak egyetlen verem adatszerkezetet használ. Algoritmusuk az óramutató járásával megegyező irányban halad végig a sokszögön, a bal szélső csúcsától kezdve. Ennek során a veremben tárolja a csúcsok konvex sorozatát, azokat, amelyekről még nem állapította meg, hogy zsebeken belül vannak. Az algoritmus minden egyes lépésnél követ egy utat a poligon mentén a verem tetejétől a következő olyan csúcsig, amely nem a verem tetejével szomszédos két zseb egyikében van. Ezután, amíg a verem felső két csúcsa ezzel az új csúccsal együtt nem konvex helyzetben van, addig a veremet kiugratja, majd végül az új csúcsot a veremre tolja. Amikor az óramutató járása eléri a kiindulási pontot, az algoritmus visszaadja a verem csúcsainak sorozatát, mint a hajótestet.