Szerkesztő:Csizmadia Viktória/próbalap

A Chan-algoritmus 2-dimenziós esetben. Itt a pontokat nem x-koordináta alapján osztja szét, hanem szabadon választva.

A Timothy M. Chanról elnevezett Chan-algoritmus optimális kimenet-érzékeny algoritmus, amellyel egy pontot tartalmazó halmaz konvex burkát lehet kiszámítani 2- és 3-dimenziós térben. A kiszámításhoz idő szükséges, ahol a konvex burok csúcsainak száma. A kétdimenziós esetben egy algoritmust (például a Graham-féle pásztázást) és a Jarvis-féle menetelést () kombinálja az optimális futásidő eléréséhez. A Chan-algoritmus arról nevezetes, hogy sokkal egyszerűbb, mint a Kirkpatrick–Seidel-algoritmus és egyszerűen kiterjeszthető a háromdimenziós térbe is. Ezt a modellt Chan-tól függetlenül Frank Nielsen is kifejlesztette a Ph.D. disszertációjában.

Algoritmus

szerkesztés

Áttekintés

szerkesztés

Az algoritmus sikeres lefutásához egyetlen   paraméterre van szükség. Tegyük fel, hogy ez egy fix érték (a valóságban  -t nem ismerjük előre, ezért több, egyre növekvő értékű   paramétert használunk, lásd később).

Az algoritmus első lépése a   halmaz tetszőleges szétosztása   darab részhalmazra  , mindben legfeljebb   ponttal. Ekkor  .

Ezután az első fázisban egy   algoritmus segítségével (például Graham-féle pásztázás) minden  -ra kiszámítja a részhalmaz konvex burkát,  -t, ahol   a részhalmaz pontjainak száma. Mivel   részhalmaz van és mindegyikben   pont, ez a fázis   időt vesz igénybe.

A második fázisban az algoritmus a Jarvis-féle menetelést hajtja végre, a már kiszámított kis konvex burkok   felhasználásával. Ennek során minden lépésben veszünk egy   pontot, amely a konvex burok része (először   lehet a   halmaz legalacsonyabb   koordinátájú pontja, amelyről biztosan tudjuk, hogy része lesz   konvex burkának), és keresünk hozzá egy olyan   pontot, hogy a   halmaz összes többi pontja a   egyenestől jobbra legyen. Itt a   jelölés azt jelenti, hogy a   halmaz konvex burkának következő pontját ( -et)   és   függvényében határozzuk meg. A   részhalmaz   konvex burka ismert, és maximum   pontot tartalmaz (az óramutató járásával megegyező, vagy ellentétes irányban felsorolva), így   bináris kereséssel kiszámítható   idő alatt. Tehát   idő alatt a   darab részhalmaz mindegyikére kiszámítható az  . Ezek után   is meghatározható a szimpla Jarvis-féle meneteléssel, viszont elég csak az   pontokat, vagyis a kis konvex burkok pontjait figyelembe venni a teljes   halmaz pontjai helyett. Azon pontok felhasználásával pedig egy újabb pont megtalálásához a Jarvis-féle menetelés futási ideje  , ami elhanyagolható az  -k kiszámításához képest. A Jarvis-féle menetelés akkor fejeződik be, ha   alkalommal megismétlődött (mivel a lényege, hogy maximum   ismétlés után mindenképp megtaláljuk a   halmaz konvex burkát, ahol   a konvex burok pontjainak száma), tehát a második fázis   időt fog igénybe venni, ami egyenlő  -val, ha   egy  -hoz közeli érték (lásd lejjebb   megválasztásának stratégiáját).

A két fázis összesen   idő alatt számítja ki az   pont konvex burkát.

Az   paraméter megválasztása

szerkesztés

Ha   szabadon választható paraméter, akkor előfordulhat, hogy  . Ebben az esetben a második fázisban   lépés után a Jarvis-féle menetelés nem fejeződik be, az  -edik pont már nem lesz benne az előre kiszámított konvex burokban. Ekkor leállítjuk a Jarvis-féle mentelést, és   idő elteltével a konvex burok még nincs kiszámítva.

Az ötlet, hogy többször is lefuttatjuk az algoritmust egyre nagyobb   értékkel.   idő alatt minden  -re vagy elbukik, vagy sikeresen lefut. Ha   túl lassan növekszik, akkor nagy lehet a szükséges iterációk száma, ellenben ha túl gyorsan, akkor az első  , amire sikeresen lefut, sokkal nagyobb lehet, mint  , így lassabbá válhat a futásidő:  .

Négyzetre emelős stratégia

szerkesztés

Egy lehetséges stratégia, hogy minden iterációnál négyzetre emeljük   értékét, maximum  -ig.  -vel kezdve, a   iterációnál   legyen. Ebben az esetben   iteráció lesz, mivel az algoritmus akkor fut le, ha

 

ha 2-es alapú logaritmust veszünk, és az algoritmus teljes futásideje

 

Háromdimenziós térben

szerkesztés

Ha háromdimenziós esetre akarjuk általánosítani, akkor a Graham-féle pásztázás helyett egy   algoritmust kell használnunk a háromdimenziós konvex burok kiszámítására, illetve a Jarvis-féle menetelés háromdimenziós változatát. A futásidő marad  .

Fordítás

szerkesztés

Ez a szócikk részben vagy egészben a Chan's algorithm című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.