Chen algoritmusa

Chen algoritmusa egy síkon egy véges ponthalmaz konvex héjának megszerkesztésére szolgáló algoritmus. Ez két lassabb algoritmus kombinációja ( Graham-szkennelés és Jarvis-csomagolás ). A Graham-szkennelés hátránya, hogy minden pontot poláris szög szerint kell rendezni, ami meglehetősen időigényes . A Jarvis burkoláshoz a domború hajótest minden egyes pontján át kell ismételni az összes pontot , ami a legrosszabb esetben megteszi . Timothy M. Chan nevéhez fűződik $O(n\log n)$ $O(nh)$ $O(n\log n)$ $h$ $O(n^{2})$ .

Az algoritmus leírása

Chen algoritmusának az az ötlete, hogy kezdetben az összes pontot darabcsoportokra osztja . Ennek megfelelően a csoportok száma egyenlő . Mindegyik csoporthoz egy domború hajótestet készítünk Graham keresésével , vagyis minden csoportnál időbe telik . $m$ $r=\left\lceil n/m\right\rceil$ $O(m\log m)$ $O(rm\log m)=O(n\log m)$

Ezután a bal alsó ponttól kiindulva egy közös Jarvis konvex hajótestet készítünk a kapott hajótestekhez. Ebben az esetben a konvex hajótest következő megfelelő pontja mögött van , mivel ahhoz, hogy a -gonban a figyelembe vett ponthoz képest maximális érintővel rendelkező pontot találjunk , elegendő költeni (a -gon pontjai polárszög szerint rendezve a Graham-szkennelő algoritmus végrehajtása során). Ennek eredményeként időbe telik , amíg megkerüli . $O(r\log m)$ $m$ $O(\log m)$ $m$ $O(hr\log m)=O\left(\left(hn/m\right)\log m\right)$

Vagyis Chan algoritmusa működik -re , és ha megkapod , akkor -ra . $O\left(\left(n+hn/m\right)\log m\right)$ $m=h$ $O(n\log h)$

Hajótest (P, m) 1) vegye . A kardinalitás diszjunktív részhalmazaira legfeljebb ;

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

P

r

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

m

2) i = 1-től r-ig tegye : (a) számítsuk ki a Graham konvex burkot ( ), tároljuk a csúcsokat egy polárisan rendezett tömbben;

P_{i}

3) vegye a bal szélső és legalacsonyabb pontot innen ;

p_{1}

P

4) k = 1 - m esetén tegye (a) ha i = 1 - r , keresse meg és jegyezze meg a pontot a maximális szöggel ;

q_{i}

P_{i}

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

(b) vegyünk egy pontot a maximális szöggel ;

p_{k+1}

q

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

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

c) ha visszaküldi ;

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

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

5) térjen vissza kicsiben, próbálja újra;

m

A pontok számának megválasztása m

Nyilvánvaló, hogy a Jarvis-bejárás, és így az egész algoritmus csak akkor fog helyesen működni, ha , de honnan tudod előre, hogy hány pont lesz a konvex hajótestben? Az algoritmust többször le kell futtatni, kiválasztva , és ha , akkor az algoritmus hibát ad vissza. Ha a kijelölést bináris kereséssel hajtja végre a -n , akkor az időhöz fog jutni, ami elég hosszú. $m\geqslant h$ $m$ $m<h$ $n$ $O((n\log h)\log n)=O(n\log n)$

A folyamat felgyorsítható, ha kis értékkel kezdjük, majd jelentősen növeljük, amíg be nem jön . Például vegyük . Ebben az esetben az -i iteráció . A keresési folyamat akkor ér véget, amikor , azaz ( a bináris 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}}$

A végén . $\sum _{{t=1}}^{{{\mathrm {lg}}\,{\mathrm {lg}}\,h}}n2^{t}=n\sum _{{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) t = 1-től n-ig tegye: a) venni ;

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

(b) L = hajótest (P, m); (c) ha L != " kicsi, próbáld újra" adja vissza L-t;

m

Irodalom

David M Mount. Számítógépes geometria. - Marylandi Egyetem, 2002. - 122 p.