Chens algoritm

Chens algoritm är en algoritm för att konstruera det konvexa skrovet av en ändlig uppsättning punkter på ett plan. Det är en kombination av två långsammare algoritmer ( Graham-skanning och Jarvis-inpackning ). Nackdelen med Graham-skanning är behovet av att sortera alla punkter efter polär vinkel, vilket är ganska tidskrävande . Jarvis-inpackning kräver iteration över alla punkter för var och en av punkterna på det konvexa skrovet , vilket i värsta fall tar . Uppkallad efter Timothy M. Chan $O(n\log n)$ $O(nh)$ $O(n\log n)$ $h$ $O(n^{2})$ .

Beskrivning av algoritmen

Tanken med Chens algoritm är att initialt dela upp alla punkter i grupper av bitar i varje. Följaktligen är antalet grupper lika med . För var och en av grupperna konstrueras ett konvext skrov genom att skanna Graham efter , det vill säga att det tar tid för alla grupper . $m$ $r=\left\lceil n/m\right\rceil$ $O(m\log m)$ $O(rm\log m)=O(n\log m)$

Sedan, med början från den nedre vänstra punkten, konstrueras ett gemensamt Jarvis konvext skrov för de resulterande skroven. I det här fallet är nästa lämpliga punkt för det konvexa skrovet bakom , eftersom för att hitta en punkt med en maximal tangent med avseende på den betraktade punkten i -gon, räcker det att spendera (punkterna i -gon var sorterade efter polär vinkel under exekveringen av Graham-skanningsalgoritmen). Som ett resultat tar det tid att ta sig runt . $O(r\log m)$ $m$ $O(\log m)$ $m$ $O(hr\log m)=O\left(\left(hn/m\right)\log m\right)$

Det vill säga, Chans algoritm fungerar för , och om du får , då för . $O\left(\left(n+hn/m\right)\log m\right)$ $m=h$ $O(n\log h)$

Skrov (P, m) 1) ta . Dela upp i disjunktiva delmängder av kardinalitet högst ;

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

P

r

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

m

2) för i = 1 till r gör : (a) beräkna Grahams konvexa skrov ( ), lagra topparna i en polärt sorterad array;

Pi}

3) ta den vänstra och lägsta punkten från ;

p_{1}

P

4) för k = 1 till m gör (a) för i = 1 till r hitta och kom ihåg punkten från med den maximala vinkeln ;

q_{i}

Pi}

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

(b) ta som en punkt från med den maximala vinkeln ;

p_{k+1}

q

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

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

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

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

5) returnera liten, försök igen;

m

Val av antal poäng m

Det är klart att Jarvis-traversalen, och därmed hela algoritmen, bara kommer att fungera korrekt om , men hur vet man i förväg hur många punkter det kommer att finnas i det konvexa skrovet? Det är nödvändigt att köra algoritmen flera gånger, välja och, om , kommer algoritmen att returnera ett fel. Om du gör urvalet genom binär sökning på , kommer du att sluta med tiden , som är ganska lång. $m\geqslant h$ $m$ $m<h$ $n$ $O((n\log h)\log n)=O(n\log n)$

Processen kan påskyndas genom att börja med ett litet värde och sedan öka det avsevärt tills det fungerar . Ta till exempel . I det här fallet tar -i iterationen . Sökprocessen avslutas när , dvs ( är den binära logaritmen). $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}}$

Till slut . $\sum _{{t=1}}^{{{\mathrm {lg}}\,{\mathrm {lg}}\,h}}n2^{t}=n\summa _{{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) för t = 1 till n gör: (a) ta ;

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

(b) L = Hull (P, m); (c) om L != " liten, försök igen" returnera L;

m

Litteratur

David M Mount. Beräkningsgeometri. - University of Maryland, 2002. - 122 sid.