Algoritmul lui Chen

Algoritmul lui Chen este un algoritm pentru construirea carcasei convexe a unui set finit de puncte pe un plan. Este o combinație de doi algoritmi mai lenți ( scanarea Graham și împachetarea Jarvis ). Dezavantajul scanării Graham este necesitatea de a sorta toate punctele după unghiul polar , ceea ce necesită destul de mult timp . Înfășurarea Jarvis necesită repetarea tuturor punctelor pentru fiecare dintre punctele carcasei convexe , ceea ce în cel mai rău caz necesită . Numit după Timothy M. Chan $O(n\log n)$ $O(nh)$ $O(n\log n)$ $h$ $O(n^{2})$ .

Descrierea algoritmului

Ideea algoritmului lui Chen este de a împărți inițial toate punctele în grupuri de bucăți din fiecare. În consecință, numărul de grupuri este egal cu . Pentru fiecare dintre grupuri, o carcasă convexă este construită prin scanarea Graham pentru , adică va dura timp pentru toate grupurile . $m$ $r=\left\lceil n/m\right\rceil$ $O(m\log m)$ $O(rm\log m)=O(n\log m)$

Apoi, pornind din punctul din stânga jos, se construiește o carcasă convexă Jarvis comună pentru corpurile rezultate. În acest caz, următorul punct potrivit pentru învelișul convex este în spatele lui , deoarece pentru a găsi un punct cu tangentă maximă față de punctul considerat din -gon, este suficient să cheltuiți (punctele din -gon au fost sortate după unghi polar în timpul execuției algoritmului de scanare Graham). Drept urmare, este nevoie de timp pentru a vă deplasa . $O(r\log m)$ $m$ $O(\log m)$ $m$ $O(hr\log m)=O\stânga(\left(hn/m\dreapta)\log m\dreapta)$

Adică, algoritmul lui Chan funcționează pentru , iar dacă obțineți , atunci pentru . $O\stanga(\stanga(n+hn/m\dreapta)\log m\dreapta)$ $m=h$ $O(n\log h)$

Cocă (P, m) 1) ia . Împărțiți în submulțimi disjunctive de cardinalitate nu mai mult de ;

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

P

r

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

m

2) pentru i = 1 la r face : (a) calculați corpul convex Graham ( ), stocați vârfurile într-o matrice sortată polar;

P_{i}

3) luați punctul cel mai din stânga și cel mai jos din ;

p_{1}

P

4) pentru k = 1 la m faceți (a) pentru i = 1 la r găsiți și amintiți - vă punctul din unghiul maxim ;

q_{i}

P_{i}

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

(b) luați ca punct din unghiul maxim ;

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) reveniți mic, încercați din nou;

m

Alegerea numărului de puncte m

Este clar că traversarea Jarvis și, prin urmare, întregul algoritm, va funcționa corect numai dacă , dar de unde știi dinainte câte puncte vor fi în carcasa convexă? Este necesar să rulați algoritmul de mai multe ori, alegând și, dacă , atunci algoritmul va returna o eroare. Dacă faceți selecția prin căutare binară pe , atunci veți ajunge cu timpul , care este destul de lung. $m\geqslant h$ $m$ $m<h$ $n$ $O((n\log h)\log n)=O(n\log n)$

Procesul poate fi accelerat pornind cu o valoare mică și apoi crescând-o semnificativ până când funcționează . De exemplu, luați . În acest caz, iterația -i va dura . Procesul de căutare se va încheia când , adică ( este logaritmul binar). $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}}$

In sfarsit . $\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) pentru t = 1 la n face: (a) ia ;

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

(b) L = Cocă (P, m); (c) dacă L != „ mic, încearcă din nou” returnează L;

m

Literatură

David M Mount. Geometrie computațională. - Universitatea din Maryland, 2002. - 122 p.