Grahams algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. juli 2020; checks kræver 5 redigeringer .

Grahams algoritme er en algoritme til at konstruere et konvekst skrog i todimensionelt rum. I denne algoritme løses det konvekse skrogproblem ved hjælp af en stak dannet af kandidatpunkter. Alle punkter i inputsættet skubbes ind på stakken, og derefter fjernes punkter, der ikke er hjørner af det konvekse skrog, til sidst fra det. I slutningen af algoritmen forbliver kun hjørnerne af skallen på stakken i den rækkefølge, de krydses mod uret.

Algoritme

Indgangsdataene for Graham-proceduren er sættet af punkter Q, hvor . Den kalder funktionen Top(S), som returnerer punktet i toppen af stakken S uden at ændre indholdet. Derudover bruges også funktionen NextToTop(S), som returnerer punktet placeret på stakken S, en position under toppunktet; stak S ændres ikke. $|Q|\geqslant 3$

Graham (Q) 1) Lad være et punkt fra mængden Q med minimumskoordinaten y eller den længst til venstre af sådanne punkter i nærvær af kampe

p_{0}

2) Lad være de resterende punkter i mængden Q, sorteret i stigende rækkefølge af den polære vinkel,

<p_{1},p_{2},\ldots ,p_{m}>

målt mod uret i forhold til punktet (hvis de polære vinkler af flere punkter er ens, så med afstanden til punktet )

p_{0}

p_{0}

3) Tryk( ,S)

p_{0}

4) Tryk( ,S)

p_{1}

5) for i = 2 til m do 6), mens vinklen dannet af punkterne NextToTop(S),Top(S) og , danner et ikke-venstresving

p_{i}

(når vi bevæger os langs den stiplede linje dannet af disse punkter, bevæger vi os lige eller til højre) 7) gør Pop(S) 8) Tryk( ,S)

p_{i}

9) returner S

For at bestemme om tre punkter danner , og en venstredrejning, kan du bruge en generalisering af vektorproduktet til et todimensionelt rum, nemlig venstresvingstilstanden vil se sådan ud: , hvor $-en$ $b$ $c$ $u_{x}v_{y}-u_{y}v_{x}\geqslant 0$ $u=\left\{b_{x}-a_{x},\;b_{y}-a_{y}\right\},v=\left\{c_{x}-b_{x} ,\;c_{y}-b_{y}\right\}$

Et eksempel på driften af Grahams algoritme.

Graham scanning korrekthed

Hvis Graham-proceduren behandler et sæt punkter Q, hvor , i slutningen af denne procedure, vil stakken S kun indeholde (fra bund til top) hjørnerne af skallen CH(Q) i rækkefølge mod uret. $|Q|\geqslant 3$

Bevis

Efter at have udført linje 2, har vi en række punkter til rådighed . Lad os definere en delmængde af punkter for i = 2,3,...,m. Sættet af punkter Q danner dem, der blev fjernet på grund af det faktum, at deres polære vinkel i forhold til punktet p0 falder sammen med den polære vinkel for et eller andet punkt fra mængden . Disse punkter hører ikke til det konvekse skrog CH(Q), så CH( ) = CH(Q). Det er således tilstrækkeligt at vise, at stakken S ved slutningen af Grahams procedure består af hjørnerne af skallen CH( ) i rækkefølge mod uret, hvis disse punkter ses op på stakken fra bund til top. Bemærk, at ligesom punkterne , , er hjørner af skallen CH(Q), er punkterne , , hjørner af skallen CH( ). $<p_{1},p_{2},\ldots ,p_{m}>$ $Q_{i}=\venstre\{p_{0},p_{1},\ldots ,p_{i}\right\}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $p_{0}$ $p_{1}$ $om eftermiddagen}$ $p_{0}$ $p_{1}$ $p_{i}$ $Q_{i}$

Beviset bruger cyklusinvarianten formuleret nedenfor. I begyndelsen af hver iteration af for-løkken i linje 6-9 består stakken S (fra bund til top) kun af hjørnerne af skallen CH( ) i rækkefølge mod uret. $Q_{{i-1}}$

Initialisering . Den første tidslinje 6 udføres, den invariante bibeholdes, fordi stakken S på det tidspunkt kun består af toppunkter = , og dette sæt af tre hjørner danner sit eget konvekse skrog. Derudover, hvis du ser punkterne nedefra og op, vil de blive placeret i rækkefølge mod uret. $Q_{2}$ $Q_{{i-1}}$

Bevaring . Når du indtaster en ny iteration af for-løkken, øverst i stakken S er punkt , placeret der i slutningen af den forrige iteration (eller før den første iteration, når i = 3). Lad være det øverste punkt på stakken S efter udførelse af linje 7-8 i while-løkken, men før punktet skubbes ind på stakken i linje 9 . Lad også være punktet placeret i stakken S direkte under punktet . I det øjeblik, hvor punktet er i toppen af stakken S, og punktet endnu ikke er tilføjet, indeholder stakken de samme punkter som efter den jth iteration af for-løkken. Derfor, ifølge sløjfe-invarianten, på dette tidspunkt, indeholder stakken S kun CH( ) i tværgående rækkefølge mod uret, set fra bund til top. Punktets polære vinkel i forhold til punktet er større end punktets polære vinkel , og da vinklen ruller til venstre (ellers ville punktet blive fjernet fra stakken), efter at punktet er tilføjet til stakken S (før der var kun knudepunkter CH( )) det vil indeholde knudepunkter CH( ). Samtidig vil de blive arrangeret i rækkefølge mod uret, hvis de ses nedefra og op. $p_{{i-1}}$ $p_{j}$ $p_{i}$ $p_{k}$ $p_{j}$ $p_{j}$ $p_{i}$ $Q_{j}$ $p_{i}$ $p_{0}$ $p_{j}$ $p_{k}$ $p_{j}$ $p_{i}$ $p_{j}$ $p_{i}$ $Q_{j}$ $Q_{j}\kop \left\{p_{i}\right\}$

Lad os vise, at mængden af toppunkter CH( ) falder sammen med sættet af punkter CH( ). Betragt et vilkårligt punkt, der poppede fra stakken under den i-te iteration af for-løkken, og lad være punktet placeret på stakken S umiddelbart under punktet før det sidste spring fra stakken (dette punkt pr kan være punktet ). Vinklen ruller ikke til venstre, og punktets polære vinkel i forhold til punktet er større end punktets polære vinkel . Da punktet er inde i trekanten dannet af tre andre punkter i mængden , kan det ikke være toppunktet for CH( ). Da det ikke er et toppunkt for CH( ), så CH( - { }) = CH( ). Lad være sættet af punkter taget fra stakken under udførelsen af den i-te iteration af for-løkken. Ligheden CH( - ) = CH( ) er sand. Men — = { }, så vi konkluderer, at CH( { }) = CH( — ) = CH( ). $Q_{j}\kop \left\{p_{i}\right\}$ $Q_{i}$ $p_{t}$ $p_{r}$ $p_{t}$ $p_{j}$ $p_{r}$ $p_{t}$ $p_{i}$ $p_{t}$ $p_{0}$ $p_{r}$ $p_{t}$ $Q_{i}$ $Q_{i}$ $p_{t}$ $Q_{i}$ $Q_{i}$ $p_{t}$ $Q_{i}$ $P_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$ $\kop$ $p_{i}$ $Q_{j}$ $\kop$ $p_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$

Umiddelbart efter at punktet er skubbet ud af stakken S , indeholder det kun hjørnerne CH( ) i den rækkefølge, de krydses mod uret, hvis man ser dem i stakken fra bund til top. Den efterfølgende stigning med én af værdien af i vil føre til bevarelsen af sløjfeinvarianten i den næste iteration. $p_{i}$ $Q_{i}$

Fuldførelse . I slutningen af sløjfen er ligheden i = m + 1 opfyldt, så det følger af sløjfeinvarianten, at stakken S kun består af hjørnerne af CH( ), det vil sige af hjørnerne af CH(Q). Disse hjørner er i tværgående rækkefølge mod uret, når de ses på stakken fra bund til top. $Q_{m}$

Åbningstider

Kørselstiden for Graham-proceduren er , hvor . Som du nemt kan se, vil while-løkken tage O( ) tid. Mens sortering af polære vinkler vil tage tid, derfor den generelle asymptotiske opførsel af Grahams procedure. $O(N\log N)$ $N=|Q|$ $N$ $O(N\log N)$

Se også

Litteratur

T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmer. Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - "Williams", 2005.