Graham algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. július 26-án felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Graham -algoritmus egy konvex hajótest felépítésére szolgáló algoritmus kétdimenziós térben. Ebben az algoritmusban a konvex hajótest problémáját a jelölt pontokból képzett verem segítségével oldjuk meg. A bemeneti halmaz összes pontja a verembe kerül, majd végül eltávolítják belőle azokat a pontokat, amelyek nem a konvex hajótest csúcsai. Az algoritmus végén csak a shell csúcsai maradnak a veremben abban a sorrendben, ahogy az óramutató járásával ellentétes irányban haladnak.

Algoritmus

A Graham-eljárás bemeneti adatai a Q pontok halmaza, ahol . Meghívja a Top(S) függvényt, amely visszaadja az S verem tetején lévő pontot anélkül, hogy annak tartalmát megváltoztatná. Ezenkívül a NextToTop(S) függvény is használatos, amely az S veremben található pontot adja vissza, egy pozícióval a felső pont alatt; verem S nem változik. $|Q|\geqslant 3$

Graham (Q) 1) Legyen egy pont a Q halmazból minimális y koordinátájú, vagy az ilyen pontok közül a bal szélső egyezések jelenlétében

p_{0}

2) Legyen a Q halmaz fennmaradó pontjai a polárszög növekvő sorrendjében,

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

a ponthoz képest az óramutató járásával ellentétes irányban mérve (ha több pont poláris szöge azonos, akkor a pont távolságával )

p_{0}

p_{0}

3) Nyomja meg ( ,S)

p_{0}

4) Push( ,S)

p_{1}

5) i = 2 -től m -ig 6) míg a NextToTop (S),Top(S) és , pontok által alkotott szög nem balra fordult

p_{i}

(a pontok által alkotott szaggatott vonal mentén haladva egyenesen vagy jobbra haladunk) 7) Pop (S) 8) Push( ,S)

p_{i}

9) küldje vissza S

Annak meghatározásához, hogy három pont képez -e , és egy balra fordulást, használhatja a vektorszorzat általánosítását egy kétdimenziós térre, nevezetesen a balra fordulás feltétele így fog kinézni: , ahol $a$ $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\}$

Példa a Graham-algoritmus működésére.

Graham szkennelés helyessége

Ha a Graham eljárás egy Q ponthalmazt dolgoz fel, ahol , akkor ennek az eljárásnak a végén az S verem (alulról felfelé) csak a CH(Q) héj csúcsait fogja tartalmazni az óramutató járásával ellentétes sorrendben. $|Q|\geqslant 3$

Bizonyítás

A 2. sor végrehajtása után egy pontsorozat áll rendelkezésünkre . Határozzuk meg az i = 2,3,…,m pontok részhalmazát . A Q pontok halmaza azokat a pontokat alkotja, amelyeket azért távolítottak el, mert a p0 ponthoz viszonyított polárszögük egybeesik a halmaz valamely pontjának polárszögével . Ezek a pontok nem tartoznak a CH(Q) konvex burokhoz, így CH( ) = CH(Q). Így elég megmutatni, hogy a Graham-eljárás végén az S verem a CH( ) héj csúcsaiból áll az óramutató járásával ellentétes sorrendben, ha ezeket a pontokat alulról felfelé nézzük a veremben. Vegyük észre, hogy ahogy a , , pontok a CH(Q) shell csúcsai, a , , pontok a CH( ) shell csúcsai. $<p_{1},p_{2},\ldots ,p_{m}>$ $Q_{i}=\left\{p_{0},p_{1},\ldots ,p_{i}\jobbra\}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $p_{0}$ $p_{1}$ $délután}$ $p_{0}$ $p_{1}$ $p_{i}$ $Q_{i}$

A bizonyítás az alábbiakban megfogalmazott ciklusinvariánst használja. A for ciklus minden iterációjának elején a 6-9. sorban az S verem (alulról felfelé) csak a CH( ) héj csúcsaiból áll az óramutató járásával ellentétes sorrendben. $Q_{{i-1}}$

Inicializálás . A 6. idősor első végrehajtása, az invariáns megmarad, mert ezen a ponton az S verem csak = csúcsokból áll , és ez a három csúcsból álló halmaz alkotja saját konvex burkot. Ezenkívül, ha a pontokat alulról felfelé nézi, akkor azok az óramutató járásával ellentétes sorrendben helyezkednek el. $Q_{2}$ $Q_{{i-1}}$

Tartósítás . A for ciklus új iterációjának megadásakor a verem tetején az S pont található , amely az előző iteráció végén (vagy az első iteráció előtt, amikor i = 3) kerül oda. Legyen az S verem legfelső pontja a while ciklus 7-8. sorainak végrehajtása után, de mielőtt a pont a verembe kerül a 9. sorban . Legyen az S veremben közvetlenül a pont alatt található pont is . Abban a pillanatban, amikor a pont az S verem tetején van, és a pontot még nem adták hozzá, a verem ugyanazokat a pontokat tartalmazza, mint a for ciklus j-edik iterációja után. Ezért a ciklusinvariáns szerint ezen a ponton az S veremben csak a CH( ) található az óramutató járásával ellentétes bejárási sorrendben, alulról felfelé nézve. A pontnak a ponthoz viszonyított poláris szöge nagyobb, mint a pont poláris szöge , és mivel a szög balra gördül (különben a pont kikerülne a veremből), miután hozzáadta a pontot az S veremhez (mielőtt csak CH( ) csúcsok voltak, a CH( ) csúcsokat fogja tartalmazni . Ugyanakkor alulról felfelé nézve az óramutató járásával ellentétes sorrendben lesznek elrendezve. $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}\csésze \left\{p_{i}\jobbra\}$

Mutassuk meg, hogy a CH( ) csúcshalmaz egybeesik a CH( ) ponthalmazsal. Tekintsünk egy tetszőleges pontot a veremből a for ciklus i-edik iterációja során, és legyen az a pont, amely az S veremben található közvetlenül a veremből való utolsó kiugrás előtti pont alatt (ez a pr pont lehet a pont ). A szög nem gördül balra, és a pont poláris szöge a ponthoz képest nagyobb, mint a pont poláris szöge . Mivel a pont a halmaz három másik pontja által alkotott háromszögön belül van , nem lehet CH( ) csúcsa. Mivel ez nem a CH( ) csúcsa , akkor CH( - { }) = CH( ). Legyen a for ciklus i-edik iterációjának végrehajtása során a veremből vett pontok halmaza. A CH( - ) = CH( ) egyenlőség igaz. Azonban — = { }, tehát arra a következtetésre jutunk, hogy CH( { }) = CH( — ) = CH( ). $Q_{j}\csésze \left\{p_{i}\jobbra\}$ $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}$ $\csésze$ $p_{i}$ $Q_{j}$ $\csésze$ $p_{i}$ $Q_{i}$ $P_{i}$ $Q_{i}$

Közvetlenül a pont S veremből való kiszorítása után csak a CH( ) csúcsokat tartalmazza az óramutató járásával ellentétes irányban való bejárásuk sorrendjében, ha alulról felfelé nézzük őket a veremben. Az i értékének ezt követő növelése a ciklusinvariáns megőrzéséhez vezet a következő iterációban. $p_{i}$ $Q_{i}$

Befejezés . A ciklus végén teljesül az i = m + 1 egyenlőség, így a ciklusinvariánsból következik, hogy az S verem csak a CH( ), vagyis a CH(Q) csúcsaiból áll. Ezek a csúcsok az óramutató járásával ellentétes bejárási sorrendben vannak, ha alulról felfelé nézzük a veremben. $Q_{m}$

Nyitva tartás

A Graham eljárás futási ideje , ahol . Amint könnyen látható, a while ciklus O( ) időt vesz igénybe. Míg a poláris szögek rendezése időt vesz igénybe , ebből adódik a Graham-eljárás általános aszimptotikus viselkedése. $O(N\log N)$ $N=|Q|$ $N$ $O(N\log N)$

Lásd még

Irodalom

T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmusok. Konstrukció és elemzés = Bevezetés az algoritmusokba. - 2. kiadás - "Williams", 2005.