From 523bcad0f9c7ec0b6579bc0ce9ba392eb136670c Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 Nov 2011 23:45:30 +0100 Subject: [PATCH] Geometrie: Spojeni dvojich starych zapisku --- old/8-geom2/8-geom2.tex => 6-geom/6-geom.tex | 133 ++++++++++++++++- {old/7-geom => 6-geom}/7-geom.mp | 0 {old/7-geom => 6-geom}/7-geom1_male_obaly.eps | 0 .../7-geom2_pridani_bodu.eps | 0 {old/7-geom => 6-geom}/7-geom3_obalky.eps | 0 .../7-geom => 6-geom}/7-geom4_determinant.eps | 0 .../7-geom5_rybi_motivace.eps | 0 .../7-geom6_provazkovy_algoritmus.eps | 0 .../7-geom7_naslednik_pres_konvexni_obal.eps | 0 {old/8-geom2 => 6-geom}/8-geom2.mp | 0 {old/8-geom2 => 6-geom}/8-geom2_0_bear.eps | 0 {old/8-geom2 => 6-geom}/8-geom2_1_usecky.eps | 0 .../8-geom2_2_polorovina.eps | 0 .../8-geom2_3_voroneho_diagram.eps | 0 .../8-geom2_4_pasy_mnohouhelniku.eps | 0 .../8-geom2_5_upravy_stromu.eps | 0 .../8-geom2_6_rychla_perzistence.eps | 0 {old/7-geom => 6-geom}/Makefile | 2 +- {old/8-geom2 => 6-geom}/lib.mp | 0 old/7-geom/7-geom.tex | 136 ------------------ old/7-geom/lib.mp | 82 ----------- old/8-geom2/Makefile | 3 - 22 files changed, 133 insertions(+), 223 deletions(-) rename old/8-geom2/8-geom2.tex => 6-geom/6-geom.tex (56%) rename {old/7-geom => 6-geom}/7-geom.mp (100%) rename {old/7-geom => 6-geom}/7-geom1_male_obaly.eps (100%) rename {old/7-geom => 6-geom}/7-geom2_pridani_bodu.eps (100%) rename {old/7-geom => 6-geom}/7-geom3_obalky.eps (100%) rename {old/7-geom => 6-geom}/7-geom4_determinant.eps (100%) rename {old/7-geom => 6-geom}/7-geom5_rybi_motivace.eps (100%) rename {old/7-geom => 6-geom}/7-geom6_provazkovy_algoritmus.eps (100%) rename {old/7-geom => 6-geom}/7-geom7_naslednik_pres_konvexni_obal.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2.mp (100%) rename {old/8-geom2 => 6-geom}/8-geom2_0_bear.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2_1_usecky.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2_2_polorovina.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2_3_voroneho_diagram.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2_4_pasy_mnohouhelniku.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2_5_upravy_stromu.eps (100%) rename {old/8-geom2 => 6-geom}/8-geom2_6_rychla_perzistence.eps (100%) rename {old/7-geom => 6-geom}/Makefile (70%) rename {old/8-geom2 => 6-geom}/lib.mp (100%) delete mode 100644 old/7-geom/7-geom.tex delete mode 100644 old/7-geom/lib.mp delete mode 100644 old/8-geom2/Makefile diff --git a/old/8-geom2/8-geom2.tex b/6-geom/6-geom.tex similarity index 56% rename from old/8-geom2/8-geom2.tex rename to 6-geom/6-geom.tex index 034b395..d2856e4 100644 --- a/old/8-geom2/8-geom2.tex +++ b/6-geom/6-geom.tex @@ -1,6 +1,137 @@ \input lecnotes.tex -\prednaska{8}{Geometrie vrací úder}{(sepsal Pavel Klavík)} +\prednaska{7}{Geometrické algoritmy}{} + +\>Uká¾eme si nìkolik základních algoritmù na øe¹ení geometrických problémù v~rovinì. Proè zrovna v~rovinì? Inu, jednorozmìrné problémy bývají triviální +a naopak pro vy¹¹í dimenze jsou velice komplikované. Rovina je proto rozumným kompromisem mezi obtí¾ností a zajímavostí. + +Celou kapitolou nás bude provázet pohádka ze ¾ivota ledních medvìdù. Pokusíme se vyøe¹it jejich \uv{ka¾dodenní} problémy~\dots + +\h{Hledání konvexního obalu} + +{\I Daleko na severu ¾ili lední medvìdi. Ve vodách tamního moøe byla hojnost ryb a jak je známo, ryby jsou oblíbenou pochoutkou ledních medvìdù. +Proto¾e medvìdi z~na¹í pohádky rozhodnì nejsou ledajací a ani chytrost jim neschází, rozhodli se v¹echny ryby pochytat. Znají pøesná místa výskytu +ryb a rádi by vyrobili obrovskou sí», do které by je v¹echny chytili. Pomozte medvìdùm zjistit, jaký nejmen¹í obvod taková sí» mù¾e mít.} + +\figure{7-geom5_rybi_motivace.eps}{Problém ledních mìdvìdù: Jaký je nejmen¹í obvod sítì?}{3in} + +Neboli v~øeèi matematické, chceme pro zadanou mno¾inu bodù v~rovinì nalézt její konvexní obal. Co je to konvexní obal? Mno¾ina bodù je {\I konvexní}, +pokud pro ka¾dé dva body obsahuje i celou úseèku mezi nimi. {\I Konvexní obal} je nejmen¹í konvexní podmno¾ina roviny, která obsahuje v¹echny zadané +body.\foot{Pamatujete si na lineární obaly ve vektorových prostorech? Lineární obal mno¾iny vektorù je nejmen¹í vektorový podprostor, který tyto +vektory obsahuje. Není náhoda, ¾e tato definice pøipomíná definici konvexního obalu. Na druhou stranu ka¾dý vektor z~lineárního obalu lze vyjádøit +jako lineární kombinaci daných vektorù. Podobnì platí i pro konvexní obaly, ¾e ka¾dý bod z~obalu je konvexní kombinací daných bodù. Ta se li¹í od +lineární v~tom, ¾e v¹echny koeficienty jsou v~intervalu $[0,1]$ a navíc souèet v¹ech koeficientù je $1$. Tento algebraický pohled mù¾e mnohé vìci +zjednodu¹it. Zkuste si dokázat, ¾e obì definice konvexního obalu jsou ekvivalentní.} Z~algoritmického hlediska nás v¹ak bude zajímat jenom jeho +hranice, kterou budeme dále oznaèovat jako konvexní obal. + +Na¹ím úkolem je nalézt konvexní obal koneèné mno¾iny bodù. To je v¾dy konvexní mnohoúhelník, navíc s~vrcholy v~zadaných bodech. Øe¹ením problému tedy +bude posloupnost bodù, které tvoøí konvexní obal. Pro malé mno¾iny je konvexní obal nakreslen na obrázku, pro více bodù je v¹ak situace mnohem +slo¾itìj¹í. + +\figure{7-geom1_male_obaly.eps}{Konvexní obaly malých mno¾in.}{3in} + +Pro jednoduchost budeme pøedpokládat, ¾e v¹echny body mají rùzné $x$-ové souøadnice. Tedy utøídìní bodù zleva doprava je urèené jednoznaènì.\foot{To si +mù¾eme dovolit pøedpokládat, nebo» se v¹emi body staèí nepatrnì pootoèit. Tím konvexní obal urèitì nezmìníme. Av¹ak jednodu¹¹í øe¹ení je naprogramovat +tøídìní lexikograficky (druhotnì podle souøadnice $y$) a vyøadit identické body.} Tím máme zaji¹tìné, ¾e existují dva body, nejlevìj¹í a +nejpravìj¹í, pro které platí následující invariant: + +\s{Invariant:} Nejlevìj¹í a nejpravìj¹í body jsou v¾dy v~konvexním obalu. + +Algoritmus na nalezení konvexního obalu funguje na následujícím jednoduchém principu, kterému se nìkdy øíká {\I zametání roviny}. Procházíme body +zleva doprava a postupnì roz¹iøujeme doposud nalezený konvexní obal o~dal¹í body. Na zaèátku bude konvexní obal jediného bodu samotný bod. Na konci +$k$-tého kroku algoritmu známe konvexní obal prvních $k$ bodù. Kdy¾ algoritmus skonèí, známe hledaný konvexní obal. Podle invariantu musíme v~$k$-tém +kroku pøidat do obalu $k$-tý nejlevìj¹í bod. Zbývá si jen rozmyslet, jak pøesnì tento bod pøidat. + +Pøidání dal¹ího bodu do konvexního obalu funguje, jak je naznaèeno na obrázku. Podle invariantu víme, ¾e bod nejvíc vpravo je souèástí konvexního +obalu. Za nìj napojíme novì pøidávaný bod. Tím jsme získali nìjaký obal, ale zpravidla nebude konvexní. To lze v¹ak snadno napravit, staèí +odebírat body, v obou smìrech podél konvexního obalu, tak dlouho, dokud nezískáme konvexní obal. Na pøíkladu z obrázku nemusíme po smìru hodinových +ruèièek odebrat ani jeden bod, obal je v poøádku. Naopak proti smìru hodinových ruèièek musíme odebrat dokonce dva body. + +\figure{7-geom2_pridani_bodu.eps}{Pøidání bodu do konvexního obalu.}{4.5in} + +Pro pøípadnou implementaci a rozbor slo¾itosti si nyní popí¹eme algoritmus detailnìji. Aby se lépe popisoval, rozdìlíme si konvexní obal na dvì èásti +spojující nejlevìj¹í a nejpravìj¹í bod obalu. Budeme jim øíkat {\I horní obálka} a {\I dolní obálka}. + +\figure{7-geom3_obalky.eps}{Horní a dolní obálka konvexního obalu.}{3.4in} + +Obì obálky jsou lomené èáry, navíc horní obálka poøád zatáèí doprava a dolní naopak doleva. Pro udr¾ování bodù v~obálkách staèí dva zásobníky. +V~$k$-tém kroku algoritmu pøidáme zvlá¹» $k$-tý bod do horní i dolní obálky. Pøidáním $k$-tého bodu se v¹ak mù¾e poru¹it smìr, ve kterém obálka +zatáèí. Proto budeme nejprve body z~obálky odebírat a $k$-tý bod pøidáme a¾ ve chvíli, kdy jeho pøidání smìr zatáèení neporu¹í. + +\s{Algoritmus:} + +\algo + +\:Setøídíme body podle $x$-ové souøadnice, oznaème body $b_1, \ldots, b_n$. +\:Vlo¾íme do horní a dolní obálky bod $b_1$: $H = D = (b_1)$. +\:Pro ka¾dý dal¹í bod $b = b_2,\ldots,b_n$: +\::Pøepoèítáme horní obálku: +\:::Dokud $\vert H\vert \ge 2$, $H = (\ldots, h_{k-1}, h_k)$ a úhel $h_{k-1} h_k b$ je orientovaný doleva: +\::::Odebereme poslední bod $h_k$ z~obálky $H$. +\:::Pøidáme bod $b$ do obálky $H$. +\::Symetricky pøepoèteme dolní obálku (s orientací doprava). +\: Výsledný obal je tvoøen body v~obálkách $H$ a $D$. + +\endalgo + +Rozebereme si èasovou slo¾itost algoritmu. Setøídit body podle $x$-ové souøadnice doká¾eme v~èase $\O(n \log n)$. Pøidání dal¹ího bodu do obálek +trvá lineárnì vzhledem k~poètu odebraných bodù. Zde vyu¾ijeme obvyklý postup: Ka¾dý bod je odebrán nejvý¹e jednou, a tedy v¹echna odebrání trvají +dohromady $\O(n)$. Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$, a pokud bychom mìli seznam bodù ji¾ utøídený, doká¾eme to dokonce v +$\O(n)$. + +\s{Algebraický dodatek:} Existuje jednoduchý postup, jak zjistit orientaci úhlu? Uká¾eme si jeden zalo¾ený na lineární algebøe. Budou se hodit +vlastnosti determinantu. Absolutní hodnota determinantu je objem rovnobì¾nostìnu urèeného øádkovými vektory matice. Dùle¾itìj¹í v¹ak je, ¾e znaménko +determinantu urèuje \uv{orientaci} vektorù, zda je levotoèivá èi pravotoèivá. Proto¾e ná¹ problém je rovinný, budeme uva¾ovat determinanty matic $2 +\times 2$. + +Uva¾me souøadnicový systém v~rovinì, kde $x$-ová souøadnice roste smìrem doprava a~$y$-ová smìrem nahoru. Chceme zjistit orientaci úhlu $h_{k-1} h_k +b$. Polo¾me $\vec u = (x_1, y_1)$ jako rozdíl souøadnic $h_k$ a~$h_{k-1}$ a podobnì $\vec v = (x_2, y_2)$ je rozdíl souøadnic $b$ a~$h_k$. Matice $M$ +je definována následovnì: +$$M = \pmatrix{\vec u \cr \vec v} = \pmatrix {x_1&y_1\cr x_2&y_2}.$$ +Úhel $h_{k-1} h_k b$ je orientován doleva, právì kdy¾ $\det M = x_1y_2 - x_2y_1$ je nezáporný,\foot{Neboli vektory $\vec u$ a $\vec v$ odpovídají +rozta¾ení a zkosení vektorù báze $\vec x = (1,0)$ a $\vec y = (0,1)$, pro nì¾ je determinant nezáporný.} a spoèítat hodnotu determinantu je jednoduché. +Mo¾né situace jsou nakresleny na obrázku. Poznamenejme, ¾e k~podobnému vzorci se lze také dostat pøes vektorový souèin vektorù $\vec u$ a $\vec v$. + +\figure{7-geom4_determinant.eps}{Jak vypadají determinanty rùzných znamének v~rovinì.}{4.6in} + +\s{©lo by to vyøe¹it rychleji?} Také vám vrtá hlavou, zda existují rychlej¹í algoritmy? Na závìr si uká¾eme nìco, co na pøedná¹ce nebylo.\foot{A také +se nebude zkou¹et.} Nejrychlej¹í známý algoritmus, jeho¾ autorem je T.~Chan, funguje v~èase $\O(n \log h)$, kde $h$ je poèet bodù le¾ících na +konvexním obalu, a pøitom je pøekvapivì jednoduchý. Zde si naznaèíme, jak tento algoritmus funguje. + +Algoritmus pøichází s~následující my¹lenkou. Pøedpokládejme, ¾e bychom znali velikost konvexního obalu $h$. Rozdìlíme body libovolnì do $\lceil {n +\over h} \rceil$ mno¾in $Q_1, \ldots, Q_k$ tak, ¾e $\vert Q_i \vert \le h$. Pro ka¾dou z~tìchto mno¾in nalezneme konvexní obal pomocí vý¹e popsaného +algoritmu. To doká¾eme pro jednu v~èase $\O(h \log h)$ a pro v¹echny v~èase $\O(n \log h)$. V druhé fázi spustíme hledání konvexního obalu pomocí +provázkového algoritmu a pro zrychlení pou¾ijeme pøedpoèítané obaly men¹ích mno¾in. Nejprve popí¹eme jeho my¹lenku. Pou¾ijeme následující pozorování: + +\s{Pozorování:} Úseèka spojující dva body $a$ a $b$ le¾í na konvexním obalu, právì kdy¾ v¹echny ostatní body le¾í pouze na jedné její +stranì.\foot{Formálnì je podmínka následující: Pøímka $ab$ urèuje dvì poloroviny. Úseèka le¾í na konvexním obalu, právì kdy¾ v¹echny body le¾í v jedné +z polorovin.} + +Algoritmu se øíká {\I provázkový}, proto¾e svojí èinností pøipomíná namotávání provázku podél konvexního obalu. Zaèneme s bodem, který na konvexním +obalu urèitì le¾í, to je tøeba ten nejlevìj¹í. V ka¾dém kroku nalezneme následující bod po obvodu konvexního obalu. To udìláme napøíklad tak, ¾e +projdeme v¹echny body a vybereme ten, který svírá nejmen¹í úhel s poslední stranou konvexního obalu. Novì pøidaná úseèka vyhovuje pozorování a proto +do konvexního obalu patøí. Po $h$ krocích se dostaneme zpìt k nejlevìj¹ímu bodu a výpoèet ukonèíme. V ka¾dém kroku potøebujeme projít v¹echny body a +vybrat následníka, co¾ doká¾eme v èase $\O(n)$. Celková slo¾itost algoritmu je tedy $\O(n \cdot h)$. + +\twofigures{7-geom6_provazkovy_algoritmus.eps}{Provázkový algoritmus.}{1.25in}{7-geom7_naslednik_pres_konvexni_obal.eps}{Hledání kandidáta v pøedpoèítaném obalu.}{2.5in} + +Provázkový algoritmus funguje, ale má jednu obrovskou nevýhodu -- je toti¾ ukrutnì pomalý. Ký¾eného zrychlení dosáhneme, pokud pou¾ijeme pøedpoèítané +konvexní obaly. Ty umo¾ní rychleji hledat následníka. Pro ka¾dou z mno¾in $Q_i$ najdeme zvlá¹» kandidáta a poté z nich vybereme toho nejlep¹ího. +Mo¾ný kandidát v¾dy le¾í na konvexním obalu mno¾iny $Q_i$. Vyu¾ijeme toho, ¾e body obalu jsou \uv{uspoøádané}, i kdy¾ trochu netypicky do kruhu. +Kandidáta mù¾eme hledat metodou pùlení intervalu, i kdy¾ detaily jsou malièko slo¾itìj¹í ne¾ je obvyklé. Jak pùlit zjistíme podle smìru zatáèení +konvexního obalu. Detaily si rozmyslí ètenáø sám. + +Èasová slo¾itost pùlení je $\O(\log h)$ pro jednu mno¾inu. Mno¾in je nejvý¹e $\O({n \over h})$, tedy následující bod konvexního obalu nalezneme v èase +$\O({n \over h} \log h)$. Celý obal nalezneme ve slibovaném èase $\O(n \log h)$. + +Popsanému algoritmu schází jedna dùle¾itá vìc: Ve skuteènosti vìt¹inou neznáme velikost $h$. Budeme proto algoritmus iterovat s~rostoucí hodnotou $h$, +dokud konvexní obal nesestrojíme. Pokud pøi slepování konvexních obalù zjistíme, ¾e konvexní obal je vìt¹í ne¾ $h$, výpoèet ukonèíme. Zbývá je¹tì +zvolit, jak rychle má $h$ rùst. Pokud by rostlo moc pomalu, budeme poèítat zbyteènì mnoho fází, naopak pøi rychlém rùstu by nás poslední fáze mohla +stát pøíli¹ mnoho. + +V~$k$-té iteraci polo¾íme $h = 2^{2^k}$. Dostáváme celkovou slo¾itost algoritmu: +$$\sum_{m=0}^{\O(\log \log h)} \O(n \log 2^{2^m}) = \sum_{m=0}^{\O(\log \log h)} \O(n \cdot 2^m) = \O(n \log h),$$ +kde poslední rovnost dostaneme jako souèet prvních $\O(\log \log h)$ èlenù geometrické øady $\sum 2^m$. \>Kdy¾ s geometrickými problémy poøádnì nezametete, ony vám to vrátí! Ale kdy¾ u¾ zametat, tak urèitì ne pod koberec a místo smetáku pou¾ijte pøímku. V této pøedná¹ce nás spolu s dvìma geometrickými problémy samozøejmì èeká pokraèování pohádky o ledních medvìdech. diff --git a/old/7-geom/7-geom.mp b/6-geom/7-geom.mp similarity index 100% rename from old/7-geom/7-geom.mp rename to 6-geom/7-geom.mp diff --git a/old/7-geom/7-geom1_male_obaly.eps b/6-geom/7-geom1_male_obaly.eps similarity index 100% rename from old/7-geom/7-geom1_male_obaly.eps rename to 6-geom/7-geom1_male_obaly.eps diff --git a/old/7-geom/7-geom2_pridani_bodu.eps b/6-geom/7-geom2_pridani_bodu.eps similarity index 100% rename from old/7-geom/7-geom2_pridani_bodu.eps rename to 6-geom/7-geom2_pridani_bodu.eps diff --git a/old/7-geom/7-geom3_obalky.eps b/6-geom/7-geom3_obalky.eps similarity index 100% rename from old/7-geom/7-geom3_obalky.eps rename to 6-geom/7-geom3_obalky.eps diff --git a/old/7-geom/7-geom4_determinant.eps b/6-geom/7-geom4_determinant.eps similarity index 100% rename from old/7-geom/7-geom4_determinant.eps rename to 6-geom/7-geom4_determinant.eps diff --git a/old/7-geom/7-geom5_rybi_motivace.eps b/6-geom/7-geom5_rybi_motivace.eps similarity index 100% rename from old/7-geom/7-geom5_rybi_motivace.eps rename to 6-geom/7-geom5_rybi_motivace.eps diff --git a/old/7-geom/7-geom6_provazkovy_algoritmus.eps b/6-geom/7-geom6_provazkovy_algoritmus.eps similarity index 100% rename from old/7-geom/7-geom6_provazkovy_algoritmus.eps rename to 6-geom/7-geom6_provazkovy_algoritmus.eps diff --git a/old/7-geom/7-geom7_naslednik_pres_konvexni_obal.eps b/6-geom/7-geom7_naslednik_pres_konvexni_obal.eps similarity index 100% rename from old/7-geom/7-geom7_naslednik_pres_konvexni_obal.eps rename to 6-geom/7-geom7_naslednik_pres_konvexni_obal.eps diff --git a/old/8-geom2/8-geom2.mp b/6-geom/8-geom2.mp similarity index 100% rename from old/8-geom2/8-geom2.mp rename to 6-geom/8-geom2.mp diff --git a/old/8-geom2/8-geom2_0_bear.eps b/6-geom/8-geom2_0_bear.eps similarity index 100% rename from old/8-geom2/8-geom2_0_bear.eps rename to 6-geom/8-geom2_0_bear.eps diff --git a/old/8-geom2/8-geom2_1_usecky.eps b/6-geom/8-geom2_1_usecky.eps similarity index 100% rename from old/8-geom2/8-geom2_1_usecky.eps rename to 6-geom/8-geom2_1_usecky.eps diff --git a/old/8-geom2/8-geom2_2_polorovina.eps b/6-geom/8-geom2_2_polorovina.eps similarity index 100% rename from old/8-geom2/8-geom2_2_polorovina.eps rename to 6-geom/8-geom2_2_polorovina.eps diff --git a/old/8-geom2/8-geom2_3_voroneho_diagram.eps b/6-geom/8-geom2_3_voroneho_diagram.eps similarity index 100% rename from old/8-geom2/8-geom2_3_voroneho_diagram.eps rename to 6-geom/8-geom2_3_voroneho_diagram.eps diff --git a/old/8-geom2/8-geom2_4_pasy_mnohouhelniku.eps b/6-geom/8-geom2_4_pasy_mnohouhelniku.eps similarity index 100% rename from old/8-geom2/8-geom2_4_pasy_mnohouhelniku.eps rename to 6-geom/8-geom2_4_pasy_mnohouhelniku.eps diff --git a/old/8-geom2/8-geom2_5_upravy_stromu.eps b/6-geom/8-geom2_5_upravy_stromu.eps similarity index 100% rename from old/8-geom2/8-geom2_5_upravy_stromu.eps rename to 6-geom/8-geom2_5_upravy_stromu.eps diff --git a/old/8-geom2/8-geom2_6_rychla_perzistence.eps b/6-geom/8-geom2_6_rychla_perzistence.eps similarity index 100% rename from old/8-geom2/8-geom2_6_rychla_perzistence.eps rename to 6-geom/8-geom2_6_rychla_perzistence.eps diff --git a/old/7-geom/Makefile b/6-geom/Makefile similarity index 70% rename from old/7-geom/Makefile rename to 6-geom/Makefile index b06fe95..219b634 100644 --- a/old/7-geom/Makefile +++ b/6-geom/Makefile @@ -1,3 +1,3 @@ -P=7-geom +P=6-geom include ../Makerules diff --git a/old/8-geom2/lib.mp b/6-geom/lib.mp similarity index 100% rename from old/8-geom2/lib.mp rename to 6-geom/lib.mp diff --git a/old/7-geom/7-geom.tex b/old/7-geom/7-geom.tex deleted file mode 100644 index d600d11..0000000 --- a/old/7-geom/7-geom.tex +++ /dev/null @@ -1,136 +0,0 @@ -\input lecnotes.tex - -\prednaska{7}{Geometrické algoritmy}{(sepsal Pavel Klavík)} - -\>Uká¾eme si nìkolik základních algoritmù na øe¹ení geometrických problémù v~rovinì. Proè zrovna v~rovinì? Inu, jednorozmìrné problémy bývají triviální -a naopak pro vy¹¹í dimenze jsou velice komplikované. Rovina je proto rozumným kompromisem mezi obtí¾ností a zajímavostí. - -Celou kapitolou nás bude provázet pohádka ze ¾ivota ledních medvìdù. Pokusíme se vyøe¹it jejich \uv{ka¾dodenní} problémy~\dots - -\h{Hledání konvexního obalu} - -{\I Daleko na severu ¾ili lední medvìdi. Ve vodách tamního moøe byla hojnost ryb a jak je známo, ryby jsou oblíbenou pochoutkou ledních medvìdù. -Proto¾e medvìdi z~na¹í pohádky rozhodnì nejsou ledajací a ani chytrost jim neschází, rozhodli se v¹echny ryby pochytat. Znají pøesná místa výskytu -ryb a rádi by vyrobili obrovskou sí», do které by je v¹echny chytili. Pomozte medvìdùm zjistit, jaký nejmen¹í obvod taková sí» mù¾e mít.} - -\figure{7-geom5_rybi_motivace.eps}{Problém ledních mìdvìdù: Jaký je nejmen¹í obvod sítì?}{3in} - -Neboli v~øeèi matematické, chceme pro zadanou mno¾inu bodù v~rovinì nalézt její konvexní obal. Co je to konvexní obal? Mno¾ina bodù je {\I konvexní}, -pokud pro ka¾dé dva body obsahuje i celou úseèku mezi nimi. {\I Konvexní obal} je nejmen¹í konvexní podmno¾ina roviny, která obsahuje v¹echny zadané -body.\foot{Pamatujete si na lineární obaly ve vektorových prostorech? Lineární obal mno¾iny vektorù je nejmen¹í vektorový podprostor, který tyto -vektory obsahuje. Není náhoda, ¾e tato definice pøipomíná definici konvexního obalu. Na druhou stranu ka¾dý vektor z~lineárního obalu lze vyjádøit -jako lineární kombinaci daných vektorù. Podobnì platí i pro konvexní obaly, ¾e ka¾dý bod z~obalu je konvexní kombinací daných bodù. Ta se li¹í od -lineární v~tom, ¾e v¹echny koeficienty jsou v~intervalu $[0,1]$ a navíc souèet v¹ech koeficientù je $1$. Tento algebraický pohled mù¾e mnohé vìci -zjednodu¹it. Zkuste si dokázat, ¾e obì definice konvexního obalu jsou ekvivalentní.} Z~algoritmického hlediska nás v¹ak bude zajímat jenom jeho -hranice, kterou budeme dále oznaèovat jako konvexní obal. - -Na¹ím úkolem je nalézt konvexní obal koneèné mno¾iny bodù. To je v¾dy konvexní mnohoúhelník, navíc s~vrcholy v~zadaných bodech. Øe¹ením problému tedy -bude posloupnost bodù, které tvoøí konvexní obal. Pro malé mno¾iny je konvexní obal nakreslen na obrázku, pro více bodù je v¹ak situace mnohem -slo¾itìj¹í. - -\figure{7-geom1_male_obaly.eps}{Konvexní obaly malých mno¾in.}{3in} - -Pro jednoduchost budeme pøedpokládat, ¾e v¹echny body mají rùzné $x$-ové souøadnice. Tedy utøídìní bodù zleva doprava je urèené jednoznaènì.\foot{To si -mù¾eme dovolit pøedpokládat, nebo» se v¹emi body staèí nepatrnì pootoèit. Tím konvexní obal urèitì nezmìníme. Av¹ak jednodu¹¹í øe¹ení je naprogramovat -tøídìní lexikograficky (druhotnì podle souøadnice $y$) a vyøadit identické body.} Tím máme zaji¹tìné, ¾e existují dva body, nejlevìj¹í a -nejpravìj¹í, pro které platí následující invariant: - -\s{Invariant:} Nejlevìj¹í a nejpravìj¹í body jsou v¾dy v~konvexním obalu. - -Algoritmus na nalezení konvexního obalu funguje na následujícím jednoduchém principu, kterému se nìkdy øíká {\I zametání roviny}. Procházíme body -zleva doprava a postupnì roz¹iøujeme doposud nalezený konvexní obal o~dal¹í body. Na zaèátku bude konvexní obal jediného bodu samotný bod. Na konci -$k$-tého kroku algoritmu známe konvexní obal prvních $k$ bodù. Kdy¾ algoritmus skonèí, známe hledaný konvexní obal. Podle invariantu musíme v~$k$-tém -kroku pøidat do obalu $k$-tý nejlevìj¹í bod. Zbývá si jen rozmyslet, jak pøesnì tento bod pøidat. - -Pøidání dal¹ího bodu do konvexního obalu funguje, jak je naznaèeno na obrázku. Podle invariantu víme, ¾e bod nejvíc vpravo je souèástí konvexního -obalu. Za nìj napojíme novì pøidávaný bod. Tím jsme získali nìjaký obal, ale zpravidla nebude konvexní. To lze v¹ak snadno napravit, staèí -odebírat body, v obou smìrech podél konvexního obalu, tak dlouho, dokud nezískáme konvexní obal. Na pøíkladu z obrázku nemusíme po smìru hodinových -ruèièek odebrat ani jeden bod, obal je v poøádku. Naopak proti smìru hodinových ruèièek musíme odebrat dokonce dva body. - -\figure{7-geom2_pridani_bodu.eps}{Pøidání bodu do konvexního obalu.}{4.5in} - -Pro pøípadnou implementaci a rozbor slo¾itosti si nyní popí¹eme algoritmus detailnìji. Aby se lépe popisoval, rozdìlíme si konvexní obal na dvì èásti -spojující nejlevìj¹í a nejpravìj¹í bod obalu. Budeme jim øíkat {\I horní obálka} a {\I dolní obálka}. - -\figure{7-geom3_obalky.eps}{Horní a dolní obálka konvexního obalu.}{3.4in} - -Obì obálky jsou lomené èáry, navíc horní obálka poøád zatáèí doprava a dolní naopak doleva. Pro udr¾ování bodù v~obálkách staèí dva zásobníky. -V~$k$-tém kroku algoritmu pøidáme zvlá¹» $k$-tý bod do horní i dolní obálky. Pøidáním $k$-tého bodu se v¹ak mù¾e poru¹it smìr, ve kterém obálka -zatáèí. Proto budeme nejprve body z~obálky odebírat a $k$-tý bod pøidáme a¾ ve chvíli, kdy jeho pøidání smìr zatáèení neporu¹í. - -\s{Algoritmus:} - -\algo - -\:Setøídíme body podle $x$-ové souøadnice, oznaème body $b_1, \ldots, b_n$. -\:Vlo¾íme do horní a dolní obálky bod $b_1$: $H = D = (b_1)$. -\:Pro ka¾dý dal¹í bod $b = b_2,\ldots,b_n$: -\::Pøepoèítáme horní obálku: -\:::Dokud $\vert H\vert \ge 2$, $H = (\ldots, h_{k-1}, h_k)$ a úhel $h_{k-1} h_k b$ je orientovaný doleva: -\::::Odebereme poslední bod $h_k$ z~obálky $H$. -\:::Pøidáme bod $b$ do obálky $H$. -\::Symetricky pøepoèteme dolní obálku (s orientací doprava). -\: Výsledný obal je tvoøen body v~obálkách $H$ a $D$. - -\endalgo - -Rozebereme si èasovou slo¾itost algoritmu. Setøídit body podle $x$-ové souøadnice doká¾eme v~èase $\O(n \log n)$. Pøidání dal¹ího bodu do obálek -trvá lineárnì vzhledem k~poètu odebraných bodù. Zde vyu¾ijeme obvyklý postup: Ka¾dý bod je odebrán nejvý¹e jednou, a tedy v¹echna odebrání trvají -dohromady $\O(n)$. Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$, a pokud bychom mìli seznam bodù ji¾ utøídený, doká¾eme to dokonce v -$\O(n)$. - -\s{Algebraický dodatek:} Existuje jednoduchý postup, jak zjistit orientaci úhlu? Uká¾eme si jeden zalo¾ený na lineární algebøe. Budou se hodit -vlastnosti determinantu. Absolutní hodnota determinantu je objem rovnobì¾nostìnu urèeného øádkovými vektory matice. Dùle¾itìj¹í v¹ak je, ¾e znaménko -determinantu urèuje \uv{orientaci} vektorù, zda je levotoèivá èi pravotoèivá. Proto¾e ná¹ problém je rovinný, budeme uva¾ovat determinanty matic $2 -\times 2$. - -Uva¾me souøadnicový systém v~rovinì, kde $x$-ová souøadnice roste smìrem doprava a~$y$-ová smìrem nahoru. Chceme zjistit orientaci úhlu $h_{k-1} h_k -b$. Polo¾me $\vec u = (x_1, y_1)$ jako rozdíl souøadnic $h_k$ a~$h_{k-1}$ a podobnì $\vec v = (x_2, y_2)$ je rozdíl souøadnic $b$ a~$h_k$. Matice $M$ -je definována následovnì: -$$M = \pmatrix{\vec u \cr \vec v} = \pmatrix {x_1&y_1\cr x_2&y_2}.$$ -Úhel $h_{k-1} h_k b$ je orientován doleva, právì kdy¾ $\det M = x_1y_2 - x_2y_1$ je nezáporný,\foot{Neboli vektory $\vec u$ a $\vec v$ odpovídají -rozta¾ení a zkosení vektorù báze $\vec x = (1,0)$ a $\vec y = (0,1)$, pro nì¾ je determinant nezáporný.} a spoèítat hodnotu determinantu je jednoduché. -Mo¾né situace jsou nakresleny na obrázku. Poznamenejme, ¾e k~podobnému vzorci se lze také dostat pøes vektorový souèin vektorù $\vec u$ a $\vec v$. - -\figure{7-geom4_determinant.eps}{Jak vypadají determinanty rùzných znamének v~rovinì.}{4.6in} - -\s{©lo by to vyøe¹it rychleji?} Také vám vrtá hlavou, zda existují rychlej¹í algoritmy? Na závìr si uká¾eme nìco, co na pøedná¹ce nebylo.\foot{A také -se nebude zkou¹et.} Nejrychlej¹í známý algoritmus, jeho¾ autorem je T.~Chan, funguje v~èase $\O(n \log h)$, kde $h$ je poèet bodù le¾ících na -konvexním obalu, a pøitom je pøekvapivì jednoduchý. Zde si naznaèíme, jak tento algoritmus funguje. - -Algoritmus pøichází s~následující my¹lenkou. Pøedpokládejme, ¾e bychom znali velikost konvexního obalu $h$. Rozdìlíme body libovolnì do $\lceil {n -\over h} \rceil$ mno¾in $Q_1, \ldots, Q_k$ tak, ¾e $\vert Q_i \vert \le h$. Pro ka¾dou z~tìchto mno¾in nalezneme konvexní obal pomocí vý¹e popsaného -algoritmu. To doká¾eme pro jednu v~èase $\O(h \log h)$ a pro v¹echny v~èase $\O(n \log h)$. V druhé fázi spustíme hledání konvexního obalu pomocí -provázkového algoritmu a pro zrychlení pou¾ijeme pøedpoèítané obaly men¹ích mno¾in. Nejprve popí¹eme jeho my¹lenku. Pou¾ijeme následující pozorování: - -\s{Pozorování:} Úseèka spojující dva body $a$ a $b$ le¾í na konvexním obalu, právì kdy¾ v¹echny ostatní body le¾í pouze na jedné její -stranì.\foot{Formálnì je podmínka následující: Pøímka $ab$ urèuje dvì poloroviny. Úseèka le¾í na konvexním obalu, právì kdy¾ v¹echny body le¾í v jedné -z polorovin.} - -Algoritmu se øíká {\I provázkový}, proto¾e svojí èinností pøipomíná namotávání provázku podél konvexního obalu. Zaèneme s bodem, který na konvexním -obalu urèitì le¾í, to je tøeba ten nejlevìj¹í. V ka¾dém kroku nalezneme následující bod po obvodu konvexního obalu. To udìláme napøíklad tak, ¾e -projdeme v¹echny body a vybereme ten, který svírá nejmen¹í úhel s poslední stranou konvexního obalu. Novì pøidaná úseèka vyhovuje pozorování a proto -do konvexního obalu patøí. Po $h$ krocích se dostaneme zpìt k nejlevìj¹ímu bodu a výpoèet ukonèíme. V ka¾dém kroku potøebujeme projít v¹echny body a -vybrat následníka, co¾ doká¾eme v èase $\O(n)$. Celková slo¾itost algoritmu je tedy $\O(n \cdot h)$. - -\twofigures{7-geom6_provazkovy_algoritmus.eps}{Provázkový algoritmus.}{1.25in}{7-geom7_naslednik_pres_konvexni_obal.eps}{Hledání kandidáta v pøedpoèítaném obalu.}{2.5in} - -Provázkový algoritmus funguje, ale má jednu obrovskou nevýhodu -- je toti¾ ukrutnì pomalý. Ký¾eného zrychlení dosáhneme, pokud pou¾ijeme pøedpoèítané -konvexní obaly. Ty umo¾ní rychleji hledat následníka. Pro ka¾dou z mno¾in $Q_i$ najdeme zvlá¹» kandidáta a poté z nich vybereme toho nejlep¹ího. -Mo¾ný kandidát v¾dy le¾í na konvexním obalu mno¾iny $Q_i$. Vyu¾ijeme toho, ¾e body obalu jsou \uv{uspoøádané}, i kdy¾ trochu netypicky do kruhu. -Kandidáta mù¾eme hledat metodou pùlení intervalu, i kdy¾ detaily jsou malièko slo¾itìj¹í ne¾ je obvyklé. Jak pùlit zjistíme podle smìru zatáèení -konvexního obalu. Detaily si rozmyslí ètenáø sám. - -Èasová slo¾itost pùlení je $\O(\log h)$ pro jednu mno¾inu. Mno¾in je nejvý¹e $\O({n \over h})$, tedy následující bod konvexního obalu nalezneme v èase -$\O({n \over h} \log h)$. Celý obal nalezneme ve slibovaném èase $\O(n \log h)$. - -Popsanému algoritmu schází jedna dùle¾itá vìc: Ve skuteènosti vìt¹inou neznáme velikost $h$. Budeme proto algoritmus iterovat s~rostoucí hodnotou $h$, -dokud konvexní obal nesestrojíme. Pokud pøi slepování konvexních obalù zjistíme, ¾e konvexní obal je vìt¹í ne¾ $h$, výpoèet ukonèíme. Zbývá je¹tì -zvolit, jak rychle má $h$ rùst. Pokud by rostlo moc pomalu, budeme poèítat zbyteènì mnoho fází, naopak pøi rychlém rùstu by nás poslední fáze mohla -stát pøíli¹ mnoho. - -V~$k$-té iteraci polo¾íme $h = 2^{2^k}$. Dostáváme celkovou slo¾itost algoritmu: -$$\sum_{m=0}^{\O(\log \log h)} \O(n \log 2^{2^m}) = \sum_{m=0}^{\O(\log \log h)} \O(n \cdot 2^m) = \O(n \log h),$$ -kde poslední rovnost dostaneme jako souèet prvních $\O(\log \log h)$ èlenù geometrické øady $\sum 2^m$. - -\bye diff --git a/old/7-geom/lib.mp b/old/7-geom/lib.mp deleted file mode 100644 index 2536305..0000000 --- a/old/7-geom/lib.mp +++ /dev/null @@ -1,82 +0,0 @@ -% implementation of figure naming and figure transparency -string name,tag; name := ""; tag := ""; -def updatefigname = - if tag="": filenametemplate (name & "%c.eps"); - else: filenametemplate (name & "%c_" & tag & ".eps"); - fi; -enddef; - -def figname(expr n) = name := n; updatefigname; enddef; -def figtag(expr t) = tag := t; updatefigname; enddef; - -picture transparent_picture; -color transparent_color; transparent_color := 0.9white; -def drawtransparent(expr num) = - transparent_picture := currentpicture; -endfig; - -if tag="": filenametemplate (name & "%c_transparent.eps"); -else: filenametemplate (name & "%c_" & tag & "_transparent.eps"); -fi; -beginfig(num); - draw transparent_picture withcolor transparent_color; -endfig; - -updatefigname; -enddef; - -def from(expr p,d,len) = - p+dir(d)*len -enddef; - -def dirs(expr p,d,len) = - p--from(p,d,len) -enddef; - -def drawvertices(expr s,n) = - for i:=s upto n: - draw vertex(PQ[i]); - endfor -enddef; - -def drawfvertices(expr s,n,flags) = - for i:=s upto n: - draw vertex(PQ[i]) flags; - endfor -enddef; - -def vertex(expr p) = p withpen pencircle scaled 4pt enddef; -def drawemptyvertex(expr p) = unfill fullcircle scaled 4pt shifted p; draw fullcircle scaled 4pt shifted p; enddef; -def drawendpointvertex(expr p) = draw vertex(p) withcolor red; draw fullcircle scaled 6pt shifted p; enddef; -def createpath(expr p) = shakepath(p, 0.015cm,0.1cm) enddef; -vardef shakepath(expr p,d,l) = - save r,b; - path r; r := point(arctime 0 of p) of p; - b := -1; - for i:=l step l until arclength(p): - r := r--(point(arctime i of p) of p)+dir(angle(direction(arctime i of p) of p rotated 90))*d*b; - b := -b; - endfor - r--point(arctime arclength(p) of p) of p -enddef; - -pen normalpen; normalpen := pencircle scaled 0.6pt; -pen boldpen; boldpen := pencircle scaled 1.5pt; -pen bolderpen; bolderpen := pencircle scaled 2pt; -def dotline = withdots scaled 0.82 withpen boldpen enddef; - -vardef unclosedbubblec(expr p,c) = - bubblec((p..reverse p..cycle),c) -enddef; - -vardef bubblec(expr p,c) = - save r; - path r; r := (point(arctime 0 of p) of p)+dir(angle(direction(arctime 0 of p) of p rotated 90))*c; - for i:=0.01cm step 0.025cm until arclength(p): - r := r..(point(arctime i of p) of p)+dir(angle(direction(arctime i of p) of p rotated 90))*c; - endfor - r..(point(arctime arclength(p) of p) of p)+dir(angle(direction(arctime arclength(p) of p) of p rotated 90))*c..cycle -enddef; - -vardef bubble(expr p) = bubblec(p,0.12cm) enddef; -vardef unclosedbubble(expr p) = unclosedbubblec(p,0.12cm) enddef; diff --git a/old/8-geom2/Makefile b/old/8-geom2/Makefile deleted file mode 100644 index 087c424..0000000 --- a/old/8-geom2/Makefile +++ /dev/null @@ -1,3 +0,0 @@ -P=8-geom2 - -include ../Makerules -- 2.39.5