Chenův algoritmus

Chenův algoritmus je algoritmus pro konstrukci konvexního trupu z konečné množiny bodů v rovině. Jedná se o kombinaci dvou pomalejších algoritmů ( Grahamovo skenování a Jarvisovo zalamování ). Nevýhodou Grahamova skenování je nutnost seřadit všechny body podle polárního úhlu, což je poměrně časově náročné . Jarvisův obal vyžaduje iteraci přes všechny body pro každý z bodů konvexního trupu , což v nejhorším případě trvá . Pojmenováno po Timothy M. Chan $O(n\log n)$ $O(nh)$ $O(n\log n)$ $h$ $O(n^{2})$ .

Popis algoritmu

Myšlenkou Chenova algoritmu je zpočátku rozdělit všechny body do skupin kusů v každém z nich. V souladu s tím je počet skupin roven . Pro každou ze skupin je konvexní trup zkonstruován skenováním Grahama pro , to znamená, že to bude nějakou dobu trvat pro všechny skupiny . $m$ $r=\left\lceil n/m\right\rceil$ $O(m\log m)$ $O(rm\log m)=O(n\log m)$

Poté, počínaje od nejnižšího levého bodu, se pro výsledné trupy zkonstruuje běžný Jarvisův konvexní trup. V tomto případě je další vhodný bod pro konvexní trup za , protože k nalezení bodu s maximální tečnou vzhledem k uvažovanému bodu v -gonu stačí utratit (body v -gonu byly seřazené podle polárního úhlu během provádění Grahamova skenovacího algoritmu). V důsledku toho trvá nějaký čas , než se dostanete kolem . $O(r\log m)$ $m$ $O(\log m)$ $m$ $O(hr\log m)=O\doleva(\doleva(hn/m\vpravo)\log m\vpravo)$

To znamená, že Chanův algoritmus funguje pro , a pokud získáte , pak pro . $O\left(\left(n+hn/m\right)\log m\right)$ $m=h$ $O(n\log h)$

Trup (P, m) 1) vzít . Rozdělte na disjunktivní podmnožiny mohutnosti ne více než ;

r=\left\lceil n/m\right\rceil

P

r

P_{1},\;P_{2},\;\ldots ,\;P_{r}

m

2) pro i = 1 až r proveďte : (a) vypočítejte Grahamův konvexní obal ( ), uložte vrcholy do polárního pole;

P_{i}

3) vezměte krajní levý a nejnižší bod z ;

p_{1}

P

4) pro k = 1 až m udělejte (a) pro i = 1 až r najděte a zapamatujte si bod s maximálním úhlem ;

Qi}

P_{i}

p_{{k-1}}p_{{k}}q_{i}

(b) vzít jako bod od s maximálním úhlem ;

p_{k+1}

q

{q_{1},\;q_{2},\;\ldots ,\;q_{r}}

p_{{k-1}}p_{{k}}q

c) v případě vrácení ;

p_{{k+1}}=p_{1}

{p_{1},\;\ldots ,\;p_{k}}

5) vraťte se malý, zkuste to znovu;

m

Volba počtu bodů m

Je jasné, že Jarvisův traversal a tím i celý algoritmus bude správně fungovat pouze tehdy , když , ale jak dopředu víte, kolik bodů bude v konvexním trupu? Algoritmus je nutné několikrát spustit, vybrat a pokud , pak algoritmus vrátí chybu. Pokud provedete výběr binárním vyhledáváním na , skončíte s časem , který je poměrně dlouhý. $m\geqslant h$ $m$ $m<h$ $n$ $O((n\log h)\log n)=O(n\log n)$

Proces lze urychlit tak, že začnete s malou hodnotou a poté ji výrazně zvýšíte, dokud to nevyjde . Například vezměte . V tomto případě bude iterace -i trvat . Proces hledání skončí, když , tj. ( je binární logaritmus). $m\geqslant h$ $2^{{2^{t}}}$ $t$ $O(n\log 2^{{2^{t}}})=O(n2^{t})$ $2^{{2^{t}}}\geqslant h$ $t=\lceil {\mathrm {lg}}\,{\mathrm {lg}}\,h\rceil$ ${\mathrm {lg}}$

Nakonec . $\sum _{{t=1}}^{{{\mathrm {lg}}\,{\mathrm {lg}}\,h}}n2^{t}=n\součet _{{t=1} }^{{\mathrm {lg}}\,{\mathrm {lg}}\,h}}2^{t}\leqslant n2^{{1+{\mathrm {lg}}\,{\mathrm {lg}}\,h}}=2n\,{\mathrm {lg}}\,h=O(n\log h)$

ChanHull (P) pro t = 1 až n: a) vzít ;

m=\min(2^{{2^{t}}},\;n)

(b) L = obal (P, m); (c) jestliže L != " malé, zkuste to znovu" return L;

m

Literatura

David M Mount. Výpočetní geometrie. - University of Maryland, 2002. - 122 s.