Grahamův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. července 2020; kontroly vyžadují 5 úprav .

Grahamův algoritmus je algoritmus pro konstrukci konvexního trupu ve dvourozměrném prostoru. V tomto algoritmu je problém konvexního trupu vyřešen pomocí zásobníku vytvořeného z kandidátských bodů. Všechny body vstupní sady jsou nasunuty na hromádku a poté jsou z ní nakonec odstraněny body, které nejsou vrcholy konvexního obalu. Na konci algoritmu zůstanou v zásobníku pouze vrcholy pláště v pořadí, v jakém se procházejí proti směru hodinových ručiček.

Algoritmus

Vstupními daty Grahamovy procedury je množina bodů Q, kde . Zavolá funkci Top(S), která vrátí bod na vrcholu zásobníku S beze změny jeho obsahu. Kromě toho se používá také funkce NextToTop(S), která vrací bod umístěný na zásobníku S, jednu pozici pod vrcholovým bodem; zásobník S se nemění. $|Q|\geqslant 3$

Graham (Q) 1) Nechť je bod z množiny Q s minimální souřadnicí y nebo z těchto bodů zcela vlevo za přítomnosti shod

p_{0}

2) Nechť jsou zbývající body množiny Q, seřazené vzestupně podle polárního úhlu,

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

měřeno proti směru hodinových ručiček vzhledem k bodu (pokud jsou polární úhly několika bodů stejné, pak podle vzdálenosti k bodu )

p_{0}

p_{0}

3) Zatlačte ( ,S)

p_{0}

4) Zatlačte ( ,S)

p_{1}

5) pro i = 2 až m do 6) zatímco úhel, který svírají body NextToTop(S),Top(S) a , tvoří nelevou zatáčku

p_{i}

(při pohybu po přerušované čáře tvořené těmito body se pohybujeme rovně nebo doprava) 7) do Pop(S) 8) Zatlačte ( ,S)

p_{i}

9) vrátit S

Chcete-li určit, zda tvoří tři body a odbočku doleva , můžete použít zobecnění vektorového součinu na dvourozměrný prostor, konkrétně podmínka odbočení doleva bude vypadat takto: , kde $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říklad fungování Grahamova algoritmu.

Grahamova správnost skenování

Pokud Grahamova procedura zpracuje množinu bodů Q, kde , pak na konci této procedury bude zásobník S obsahovat (zdola nahoru) pouze vrcholy pláště CH(Q) v protisměru hodinových ručiček. $|Q|\geqslant 3$

Důkaz

Po provedení řádku 2 máme k dispozici sekvenci bodů . Definujme podmnožinu bodů pro i = 2,3,…,m. Množina bodů Q tvoří ty, které byly odstraněny kvůli skutečnosti, že jejich polární úhel vzhledem k bodu p0 se shoduje s polárním úhlem některého bodu z množiny . Tyto body nepatří do konvexního obalu CH(Q), takže CH( ) = CH(Q). Stačí tedy ukázat, že na konci Grahamova postupu se zásobník S skládá z vrcholů pláště CH( ) v pořadí proti směru hodinových ručiček, pokud se tyto body podíváme na hromádku zdola nahoru. Všimněte si, že stejně jako body , , jsou vrcholy pláště CH(Q), body , , jsou vrcholy pláště CH( ). $<p_{1},p_{2},\ldots ,p_{m}>$ $Q_{i}=\left\{p_{0},p_{1},\ldots ,p_{i}\vpravo\}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $p_{0}$ $p_{1}$ $odpoledne}$ $p_{0}$ $p_{1}$ $p_{i}$ $Qi}$

Důkaz používá níže formulovaný invariant cyklu. Na začátku každé iterace cyklu for na řádcích 6-9 se zásobník S skládá (odspodu nahoru) pouze z vrcholů pláště CH( ) v pořadí proti směru hodinových ručiček. $Q_{{i-1}}$

Inicializace . Provede se první časová přímka 6, invariant je zachován, protože v tomto bodě se zásobník S skládá pouze z vrcholů = a tato sada tří vrcholů tvoří svůj vlastní konvexní obal. Pokud si navíc body prohlížíte zdola nahoru, budou umístěny v pořadí proti směru hodinových ručiček. $Q_{2}$ $Q_{{i-1}}$

Zachování . Při zadávání nové iterace cyklu for je v horní části zásobníku S bod , umístěný tam na konci předchozí iterace (nebo před první iterací, když i = 3). Nechť je horním bodem zásobníku S po provedení řádků 7-8 smyčky while, ale předtím, než je bod nasunut na zásobník v řádku 9 . Dovolit být také bod umístěný v zásobníku S přímo pod bodem . V okamžiku, kdy je bod na vrcholu zásobníku S a bod ještě není přidán, obsahuje zásobník stejné body jako po j-té iteraci cyklu for. Proto podle invariantu smyčky v tomto bodě zásobník S obsahuje pouze CH( ) v pořadí průchodu proti směru hodinových ručiček, při pohledu zdola nahoru. Polární úhel bodu vzhledem k bodu je větší než polární úhel bodu , a protože se úhel stáčí doleva (jinak by byl bod odstraněn ze zásobníku), po přidání bodu do zásobníku S (předtím byly tam pouze vrcholy CH( )) bude obsahovat vrcholy CH( ). Zároveň budou uspořádány proti směru hodinových ručiček, při pohledu zdola nahoru. $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}\pohár \left\{p_{i}\right\}$

Ukažme, že množina vrcholů CH( ) se shoduje s množinou bodů CH( ). Uvažujme libovolný bod vyskakovaný ze zásobníku během i-té iterace cyklu for a nechť je bod umístěný na zásobníku S bezprostředně pod bodem před posledním vyskočením ze zásobníku (tímto bodem pr může být bod ). Úhel se netočí doleva a polární úhel bodu vzhledem k bodu je větší než polární úhel bodu . Protože bod je uvnitř trojúhelníku tvořeného třemi dalšími body množiny , nemůže být vrcholem CH( ). Protože to není vrchol CH( ), pak CH( - { }) = CH( ). Dovolit je množina bodů odebraných ze zásobníku během provádění i-té iterace cyklu for. Rovnost CH( - ) = CH( ) platí. Nicméně — = { }, takže dojdeme k závěru, že CH( { }) = CH( — ) = CH( ). $Q_{j}\pohár \left\{p_{i}\right\}$ $Qi}$ $p_{t}$ $p_{r}$ $p_{t}$ $p_{j}$ $p_{r}$ $p_{t}$ $p_{i}$ $p_{t}$ $p_{0}$ $p_{r}$ $p_{t}$ $Qi}$ $Qi}$ $p_{t}$ $Qi}$ $Qi}$ $p_{t}$ $Qi}$ $P_{i}$ $Qi}$ $P_{i}$ $Qi}$ $Qi}$ $P_{i}$ $Qi}$ $\pohár$ $p_{i}$ $Q_{j}$ $\pohár$ $p_{i}$ $Qi}$ $P_{i}$ $Qi}$

Ihned po vysunutí bodu ze zásobníku S obsahuje pouze vrcholy CH( ) v pořadí, v jakém se procházejí proti směru hodinových ručiček, pokud se na ně podíváte v zásobníku zdola nahoru. Následné zvýšení o jednu z hodnot i povede k zachování invariantu smyčky v další iteraci. $p_{i}$ $Qi}$

Dokončení . Na konci smyčky je splněna rovnost i = m + 1, takže z invariantu smyčky vyplývá, že zásobník S se skládá pouze z vrcholů CH( ), tedy z vrcholů CH(Q). Tyto vrcholy jsou v pořadí průchodu proti směru hodinových ručiček při pohledu na hromádku zdola nahoru. $Q_{m}$

Otevírací doba

Průběh Grahamova postupu je , kde . Jak můžete snadno vidět, smyčka while bude trvat O( ) čas. Zatímco třídění polárních úhlů bude nějakou dobu trvat , proto je Grahamova procedura obecně asymptotická. $O(N\log N)$ $N=|Q|$ $N$ $O(N\log N)$

Viz také

Literatura

T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmy. Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - "Williams", 2005.