Chan-algoritmus

A Chan-algoritmus 2-dimenziós esetben. Itt a pontokat x-koordináta alapján osztottuk szét, míg az igazi algoritmus tetszőleges szétosztásra is működik.

A Timothy M. Chanról elnevezett Chan-algoritmus optimális kimenetérzékeny algoritmus, amellyel egy $n$ pontot tartalmazó $P$ halmaz konvex burkát lehet kiszámítani 2- és 3-dimenziós térben. A kiszámításhoz $O(n\log h)$ idő szükséges, ahol $h$ a konvex burok csúcsainak száma. A kétdimenziós esetben egy $O(n\log n)$ algoritmust (például a Graham-féle pásztázást) és a Jarvis-féle menetelést ($O(nh)$) kombinálja az optimális $O(n\log h)$ 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 Chantól függetlenül Frank Nielsen is kifejlesztette a Ph.D. disszertációjában.

Algoritmus

Áttekintés

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

Az algoritmus első lépése a $P$ halmaz tetszőleges szétosztása $K\le 1+n/m$ darab részhalmazra $(Q_k{)}_{k=1,2,...K}$, mindben legfeljebb $m$ ponttal. Ekkor $K=O(n/m)$.

Ezután az első fázisban egy $O(p\log p)$ algoritmus segítségével (például Graham-féle pásztázás) minden $Q_k$-ra kiszámítja a részhalmaz konvex burkát, $C_k$-t, ahol $p$ a részhalmaz pontjainak száma. Mivel $K$ részhalmaz van és mindegyikben $O(m)$ pont, ez a fázis $K\cdot O(m\log m)=O(n\log m)$ 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 $(C_k{)}_{k=1,2,...K}$ felhasználásával. Ennek során minden lépésben veszünk egy $p_i$ pontot, amely a konvex burok része (először $p_i$ lehet a $P$ halmaz legalacsonyabb $y$ koordinátájú pontja, amelyről biztosan tudjuk, hogy része lesz $P$ konvex burkának), és keresünk hozzá egy olyan $p_{i+1}=f(p_i,P)$ pontot, hogy a $P$ halmaz összes többi pontja a $p_i{p}_{i+1}$ egyenestől jobbra legyen. Itt a $p_{i+1}=f(p_i,P)$ jelölés azt jelenti, hogy a következő pontot ($p_{i+1}$-et) $p_i$ és $P$ függvényében határozzuk meg. A $Q_k$ részhalmaz $C_k$ konvex burka ismert, és maximum $m$ pontot tartalmaz (az óramutató járásával megegyező, vagy ellentétes irányban felsorolva), így $f(p_i,Q_k)$ bináris kereséssel kiszámítható $O(\log m)$ idő alatt. Tehát $O(K\log m)$ idő alatt a $K$ darab részhalmaz mindegyikére kiszámítható az $f(p_i,Q_k)$. Ezek után $f(p_i,P)$ is meghatározható a szimpla Jarvis-féle meneteléssel, viszont elég csak az $(f(p_i,Q_k){)}_{1\le k\le K}$ pontokat, vagyis a kis konvex burkok pontjait figyelembe venni a teljes $P$ 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 $O(K)$, ami elhanyagolható az $f(p_i,Q_k)$-k kiszámításához képest. A Jarvis-féle menetelés akkor fejeződik be, ha $O(h)$ alkalommal megismétlődött (mivel a lényege, hogy maximum $h$ ismétlés után mindenképp megtaláljuk a $P$ halmaz konvex burkát, ahol $h$ a konvex burok pontjainak száma), tehát a második fázis $O(Kh\log m)$ időt fog igénybe venni, ami egyenlő $O(n\log h)$-val, ha $m$ egy $h$-hoz közeli érték (lásd lejjebb $m$ megválasztásának stratégiáját).

A két fázis összesen $O(n\log h)$ idő alatt számítja ki az $n$ pont konvex burkát.

Az $m$ paraméter megválasztása

Ha $m$ szabadon választható paraméter, akkor előfordulhat, hogy $m<h$. Ebben az esetben a második fázisban $m$ lépés után leállítjuk a Jarvis-féle mentelést, hogy ne legyen túl nagy a futásidő, és $O(n\log m)$ idő elteltével a konvex burok még nem lesz kiszámítva.

Ezért azt az ötletet alkalmazzuk, hogy többször is lefuttatjuk az algoritmust egyre nagyobb $m$ értékkel. A futás minden $m$-re $O(n\log m)$ idő alatt befejeződik (eredményesen vagy eredménytelenül). Ha $m$ 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ő $m$, amire sikeresen lefut, sokkal nagyobb lehet, mint $h$, így lassabbá válhat a futásidő: $O(n\log m)>O(n\log h)$.

Négyzetre emelős stratégia

Egy lehetséges stratégia, hogy minden iterációnál négyzetre emeljük $m$ értékét, maximum $n$-ig. $m=2$-vel kezdve, a $t.$ iterációnál $m=\min (n,2^{2^t})$ legyen. Ebben az esetben $O(\log \log h)$ iteráció lesz, mivel az algoritmus befejeződik, amint

$m=2^{2^t}\ge h⟺\log \left(2^{2^t}\right)\ge \log h⟺2^t\ge \log h⟺\log 2^t\ge \log \log h⟺t\ge \log \log h,$

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

$\sum _{t=1}^{\lceil \log \log h\rceil }O(n\log \left(2^{2^t}\right))=O(n)\sum _{t=1}^{\lceil \log \log h\rceil }O(2^t)=O(n\cdot 2^{1+\lceil \log \log h\rceil })=O(n\log h).$

Háromdimenziós térben

Ha háromdimenziós esetre akarjuk általánosítani, akkor a Graham-féle pásztázás helyett egy $O(n\log n)$ 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 $O(n\log h)$.