X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=7-geom%2F7-geom.tex;h=115f6749abca8428a9b1ac4d467f3d1588aaaeda;hb=5fa108f9e9a17fedc1be8cb2a79c1e2b25ec8256;hp=96d3abdb3b2ec40862d468654a9c5e62bd182b53;hpb=3052ceb7c0e07c9e5db71a5cdb47d385d37e9ea3;p=ads2.git

diff --git a/7-geom/7-geom.tex b/7-geom/7-geom.tex
index 96d3abd..115f674 100644
--- a/7-geom/7-geom.tex
+++ b/7-geom/7-geom.tex
@@ -1,6 +1,6 @@
 \input lecnotes.tex
 
-\prednaska{7}{Geometrické algoritmy}{(P. Klavík)}
+\prednaska{7}{Geometrické algoritmy}{(sepsal Pavel Klavík)}
 
 \>Uká¾eme si nìkolik základních algoritmù na øe¹ení geometrický 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í.
@@ -76,12 +76,13 @@ zat
 
 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 $\O(n)$.
+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 pøíslu¹ného rovnobì¾nostìnu tvoø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$.
+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$
@@ -93,9 +94,9 @@ Mo
 
 \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? 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.
+\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