Chenin algoritmi

Chenin algoritmi on algoritmi tason äärellisen pistejoukon kuperan rungon rakentamiseen. Se on kahden hitaamman algoritmin yhdistelmä ( Graham-skannaus ja Jarvis-kääre ). Graham-skannauksen haittana on tarve lajitella kaikki pisteet napakulman mukaan, mikä on melko aikaa vievää . Jarvis-käärintä vaatii iteroinnin kaikissa kuperan rungon pisteissä , mikä pahimmassa tapauksessa kestää . Nimetty Timothy M. Chanin mukaan $O(n\log n)$ $O(nh)$ $O(n\log n)$ $h$ $O(n^{2})$ .

Algoritmin kuvaus

Chenin algoritmin ideana on aluksi jakaa kaikki pisteet kappaleryhmiin kussakin. Vastaavasti ryhmien lukumäärä on yhtä suuri kuin . Jokaiselle ryhmälle muodostetaan kupera runko skannaamalla Graham for , eli se vie aikaa kaikilta ryhmiltä . $m$ $r=\left\lceil n/m\oikea\rceil$ $O(m\log m)$ $O(rm\log m)=O(n\log m)$

Sitten alhaisimmasta vasemmasta pisteestä alkaen muodostetaan yhteinen Jarvis-kupera runko tuloksena oleville rungoille. Tässä tapauksessa seuraava kuperalle rungolle sopiva piste on takana , koska pisteen löytämiseksi, jolla on maksimitangentti suhteessa tarkasteltavaan -gonin pisteeseen, riittää kuluttaminen ( -gon pisteet olivat lajiteltu napakulman mukaan Graham-skannausalgoritmin suorittamisen aikana). Tämän seurauksena kiertäminen vie aikaa . $O(r\log m)$ $m$ $O(\log m)$ $m$ $O(hr\log m)=O\left(\left(hn/m\right)\log m\right)$

Eli Chanin algoritmi toimii , ja jos saat , niin . $O\left(\left(n+hn/m\right)\log m\right)$ $m=h$ $O(n\log h)$

runko (P, m) 1) ota . Jaa kardinalisuuden disjunktiivisiin osajoukkoon enintään ;

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

P

r

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

m

2) jos i = 1 - r tee : (a) laske Grahamin konveksi runko ( ), tallenna pisteet polaarisesti lajiteltuun taulukkoon;

P_{i}

3) ottaa vasen ja alin piste kohteesta ;

p_{1}

P

4) k = 1 - m tee (a) i = 1 - r etsi ja muista piste maksimikulmalla ;

q_{i}

P_{i}

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

(b ) ottaa pisteeksi suurimmalla kulmalla ;

p_{k+1}

q

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

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

c) jos palautus ;

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

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

5) palauta pieni, yritä uudelleen;

m

Pisteiden määrän valinta m

On selvää, että Jarvis-läpikulku ja siten koko algoritmi toimii oikein vain jos , mutta mistä tiedät etukäteen kuinka monta pistettä kuperassa rungossa on? Algoritmi on suoritettava useita kertoja valitsemalla ja jos , niin algoritmi palauttaa virheen. Jos teet valinnan binäärihaulla , niin päädyt ajan kanssa , joka on melko pitkä. $m\geqslant h$ $m$ $m<h$ $n$ $O((n\log h)\log n)=O(n\log n)$

Prosessia voidaan nopeuttaa aloittamalla pienestä arvosta ja lisäämällä sitä sitten merkittävästi, kunnes se toimii . Ota esimerkiksi . Tässä tapauksessa -i-iteraatio kestää . Hakuprosessi päättyy, kun , eli ( on binäärilogaritmi). $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}}$

Lopulta . $\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) , kun t = 1 - n, tee: a) ottaa ;

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

(b) L = runko (P, m); (c) jos L != " pieni, yritä uudelleen" palauttaa L;

m

Kirjallisuus

David M Mount. Laskennallinen geometria. - Marylandin yliopisto, 2002. - 122 s.