Korektury od Martina Pecky.

[ads2.git] / 7-geom / 7-geom.tex

diff --git a/7-geom/7-geom.tex b/7-geom/7-geom.tex
index 87e94710f4eec12edbe56b5d902ddf40194951ac..d600d111d059092708a4392e882cfd49aeda30dc 100644 (file)
--- a/7-geom/7-geom.tex
+++ b/7-geom/7-geom.tex
@@ -2,7 +2,7 @@
 
 \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í
+\>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
@@ -110,7 +110,7 @@ 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 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
+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}