\prednaska{9}{Geometrické algoritmy}{(B. Maslowski, J. Návrat, M. Sta¹a)}
-
\>Budeme se teï bavit o geometrických problémech v~rovinì. Vìt¹ina algoritmù, které zde uvedeme má své obdoby sice i pro prostory vy¹¹í nebo ni¾¹í dimenze. Jednorozmìrné pøípady ale bývají triviální a vícerozmìrné jsou zase vìt¹inou moc slo¾ité.
Budeme se tedy zabývat tím, jak tyto problémy øe¹it v~dimenzi dva (v~Euklidovské rovinì).
Kouknìme se na obrázek, fialový bod le¾í na ka¾dé parabole. Speciálnì tedy ta tøi
ohniska parabol jsou vzdálena stejnì a le¾í na kru¾nici. Stane se nám to pravì tehdy,
kdy¾ se nám zametací pøímka dotkne kru¾nice, která je urèena právì tìmito tøemi
-ohnisky. Tuto událost nazveme kru¾nicová.
-\figure{kruznicova.eps}{Kru¾nicová událost.}{3in}
-
+ohnisky. Tuto událost nazveme kru¾nicová. Pojïme si to ukázat lépe na následujících
+dvou obrázcích. První pøedstavuje situaci pøed kru¾nicovou událostí, druhý je pak
+právì ona záhadná kru¾nicová událost.
+\figure{kruznicova.eps}{Pøed kru¾nicovou událostí.}{3in}
+\figure{kruznicovakonec.eps}{Kru¾nicová událost.}{3in}
\s{Datové struktury}
-Budeme potøebovat haldu událostí (místních i kru¾nicových dohromady), ta nám zabere $\O(\log n)$ pamìti.
+Budeme potøebovat haldu událostí (místních i kru¾nicových dohromady), ta nám
+zabere $\O(\log n)$ pamìti.
-Dále bude zapotøebí si udr¾ovat na¹i pobøe¾ní linii neboli posloupnost míst v~ohniscích parabolických obloukù. Zde je potøeba si definovat operace {\I Insert,Delete} a {\I FindX.} Navíc budeme potøebovat vyhledávací strom nad prùseèíky s implicitní reprezentací. Zdá se, ¾e je toho hodnì, ale v¹echno to zvládneme s pamìtí $\O(\log n).$
+Dále bude zapotøebí si udr¾ovat na¹i pobøe¾ní linii neboli posloupnost míst
+v~ohniscích parabolických obloukù. Zde je potøeba si definovat operace
+{\I Insert,Delete} a {\I FindX.} Navíc budeme potøebovat vyhledávací strom nad
+prùseèíky s implicitní reprezentací. Zdá se, ¾e je toho hodnì, ale v¹echno to
+zvládneme s pamìtí $\O(\log n).$
-Poslední datovou strukturou bude samotný diagram, reprezentovaný grafem se souøadnicemi a vazbami hran na prùseèík.
+Poslední datovou strukturou bude samotný diagram, reprezentovaný grafem se
+souøadnicemi a vazbami hran na prùseèík.
\s{Fortunùv~algoritmus}
\s{Slo¾itost:}
-Poèet místních událostí je roven $n$ a poèet kru¾nicových událostí není vìt¹í ne¾ $n$ (s ka¾dou místní událostí zanikne kru¾nicová), neboli velikost $P$ není vìt¹í ne¾ $2n$ a tedy je v¾dy lineární. Zároveò velikost $H$ není vìt¹í ne¾ $2n$, proto¾e aèkoliv~poèet místních událostí je $n$, tak v~$H$ je záznam pro ka¾dou trojici a tedy v~$H$ je maximálnì $2n$ událostí najednou. Zbývá nám tedy zjistit velikost diagramu $D$, ale ten se urèitì vejde do $\O(n)$ pamìti.
+Poèet místních událostí je roven $n$ a poèet kru¾nicových událostí není vìt¹í ne¾
+$n$ (s ka¾dou místní událostí zanikne kru¾nicová), neboli velikost $P$ není vìt¹í
+ne¾ $2n$ a tedy je v¾dy lineární. Zároveò velikost $H$ není vìt¹í ne¾ $2n$,
+proto¾e aèkoliv~poèet místních událostí je $n$, tak v~$H$ je záznam pro ka¾dou
+trojici a tedy v~$H$ je maximálnì $2n$ událostí najednou. Zbývá nám tedy zjistit
+velikost diagramu $D$, ale ten se urèitì vejde do $\O(n)$ pamìti.
Pokud tedy shrneme v¹echny na¹e odhady, pak èasová slo¾itost algoritmu je
$\O(n \log n)$ a prostorová $\O(n)$.
projects / ads2.git / blobdiff