Chan-algoritmus

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

A Timothy M. Chanról elnevezett Chan-algoritmus optimális kimenetérzékeny algoritmus, amellyel egy ${\displaystyle n}$ pontot tartalmazó ${\displaystyle P}$ halmaz konvex burkát lehet kiszámítani 2- és 3-dimenziós térben. A kiszámításhoz ${\displaystyle O(n\log h)}$ idő szükséges, ahol ${\displaystyle h}$ a konvex burok csúcsainak száma. A kétdimenziós esetben egy ${\displaystyle O(n\log n)}$ algoritmust (például a Graham-féle pásztázást) és a Jarvis-féle menetelést (${\displaystyle O(nh)}$) kombinálja az optimális ${\displaystyle 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 ${\displaystyle m\geq h}$ paraméterre van szükség. Tegyük fel, hogy ez egy fix érték (a valóságban ${\displaystyle h}$-t nem ismerjük előre, ezért több, egyre növekvő értékű ${\displaystyle m}$ paramétert használunk, lásd később).

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

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

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

Az ${\displaystyle m}$ paraméter megválasztása

Ha ${\displaystyle m}$ szabadon választható paraméter, akkor előfordulhat, hogy ${\displaystyle m<h}$. Ebben az esetben a második fázisban ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle m}$ értékkel. A futás minden ${\displaystyle m}$-re ${\displaystyle O(n\log m)}$ idő alatt befejeződik (eredményesen vagy eredménytelenül). Ha ${\displaystyle 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ő ${\displaystyle m}$, amire sikeresen lefut, sokkal nagyobb lehet, mint ${\displaystyle h}$, így lassabbá válhat a futásidő: ${\displaystyle 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 ${\displaystyle m}$ értékét, maximum ${\displaystyle n}$-ig. ${\displaystyle m=2}$-vel kezdve, a ${\displaystyle t.}$ iterációnál ${\displaystyle m=\min \left(n,2^{2^{t}}\right)}$ legyen. Ebben az esetben ${\displaystyle O(\log \log h)}$ iteráció lesz, mivel az algoritmus befejeződik, amint

${\displaystyle m=2^{2^{t}}\geq h\iff \log \left(2^{2^{t}}\right)\geq \log h\iff 2^{t}\geq \log h\iff \log {2^{t}}\geq \log {\log h}\iff t\geq \log {\log h},}$

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

${\displaystyle \sum _{t=1}^{\lceil \log \log h\rceil }O\left(n\log \left(2^{2^{t}}\right)\right)=O(n)\sum _{t=1}^{\lceil \log \log h\rceil }O(2^{t})=O\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)=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 ${\displaystyle 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 ${\displaystyle O(n\log h)}$.

Fordítá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.