\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ì).
\h{Hledání konvexního obalu}
Ptáte se o co pùjde? Zkusme si to pøiblí¾it na problému ledních medvìdù :)
-{\I Lední medvìdi si po dlouhé dobì zmapovaly vody severního moøe a zjistili pøesnì místa, kde se nacházejí jejich oblíbené ryby. No a proto¾e to jsou medvìdi chytøí tak se rozhodli v¹echny tyto rybky pochytat najednou do jedné veliké sítì. A problém, který tady mají je takovýto: Jaký nejmen¹í obvod mù¾e mít taková sí», aby se dovnitø ve¹ly je¹tì v¹echny rybky?!}
+{\I Lední medvìdi si po dlouhé dobì zmapovali vody severního moøe a zjistili pøesnì místa, kde se nacházejí jejich oblíbené ryby. No a proto¾e to jsou medvìdi chytøí, rozhodli se v¹echny tyto rybky pochytat najednou do jedné velké sítì. A problém, který tady mají, je následující: jaký nejmen¹í obvod mù¾e mít taková sí», aby se dovnitø ve¹ly je¹tì v¹echny rybky?!}
Neboli budeme øe¹it, jak nìjakou zadanou mno¾inu bodù v~rovinì obalit co nejkrat¹í uzavøenou køivkou, do které by se je¹tì v¹echny body ve¹ly.
-Intuice nám napovídá ¾e výsledek bude nìjaký konvexní\foot{Mno¾ina bodù v~rovinì je konvexní útvar, pokud platí ¾e pro ka¾dé dva body této mno¾iny je úseèka spojující tyto dva body také celá v~této mno¾inì} mnohouhelník, který bude mít vrcholy v~nìkterých uvedených bodech. Ostatní vrcholy pak budou buï nìkde na hranách mnohouhelníku, nebo uvnitø.
+Intuice nám napovídá ¾e výsledek bude nìjaký konvexní\foot{Mno¾ina bodù v~rovinì je konvexní útvar, pokud platí ¾e pro ka¾dé dva body této mno¾iny je úseèka spojující tyto dva body také celá v~této mno¾inì} mnohoúhelník, který bude mít vrcholy v~nìkterých uvedených bodech. Ostatní vrcholy pak budou buï nìkde na hranách mnohoúhelníku, nebo uvnitø.
\>Mo¾ná by se teï hodilo pøedvést názornì jak vypadají nejmen¹í konvexní obaly:
\:konvexní obal prázdné mno¾iny je prázdná mno¾ina
\:konvexní obal 1 bodu je bod samotný
\:konvexní obal 2 bodù je úseèka spojující tyto body
-\:konvexní obal 3 bodù je trojuhleník s vrcholy v~tìchto bodech
+\:konvexní obal 3 bodù je trojúhleník s vrcholy v~tìchto bodech
\:konvexní obal 4 bodù \dots to u¾ je slo¾itìj¹í
\endlist
-Konvexní obaly 4 a více bodù, jak si mù¾em v¹imnout, u¾ nejsou jednoznaèné. Pro $N$-prvkovou mno¾inu bude konvexní obal mnohouhelník se tøema a¾ $N$ vrcholy.
+Konvexní obaly 4 a více bodù, jak si mù¾em v¹imnout, u¾ nejsou jednoznaèné. Pro $N$-prvkovou mno¾inu bude konvexní obal mnohoúhelník se tøemi a¾ $N$ vrcholy.
Jeden dobrý zpùsob jak tento konvexní obal sestrojit se nazývá {\I Zametání roviny.}
Budeme takto potkávat body které le¾í v~na¹í mno¾inì.
v~ka¾dém okam¾iku budeme chtít, aby v~té èásti kterou jsme ji¾ zametli, jsme u¾ mìli spoèítaný konvexní obal. V¾dycky kdy¾ pak zametací pøímkou narazíme na nový bod, tak si u¾ jen rozmyslíme jak ho do toho konvexního obalu pøidat.
-BÚNO tady v¹ude bereme body v~obecné poloze, tedy takové, ¾e ¾ádné tøi nele¾í na jedné pøímce. Dál taky budem pøedpokládat ¾e budeme zametat ve smìru $X$-ové osy a ¾e v¹echny body mají rùznou $X$-ovou souøadnici.
+BÚNO tady v¹ude bereme body v~obecné poloze, tedy takové, ¾e ¾ádné tøi nele¾í na~jedné pøímce. Dál taky budem pøedpokládat ¾e budeme zametat ve smìru $X$-ové osy a ¾e v¹echny body mají rùznou $X$-ovou souøadnici.
Jde také vidìt ¾e bod s nejmen¹í a nejvìt¹í $X$-ovou souøadnicí bude le¾et v~konvexním obalu.
\s{Algoritmus:}
\algo
\:Setøídíme body podle jejich $X$-ové souøadnice.
-\:Vezmem první tøi body a sestojíme jejich konvexní obal.
+\:Vezmem první tøi body a sestrojíme jejich konvexní obal.
\:Opakuj: Najdeme dal¹í bod a podíváme se jestli ho mù¾eme do konvexního obalu rovnou pøidat:
\::Pokud jej mù¾eme rovnou pøidat, tak jej pøidáme.
\::Pokud jej pøidat rovnou nemù¾eme, pak je potøeba nejdøív~nìjaké body odzadu odebrat a pak teprv~pøipojit ná¹ nový bod .
\h{Voroného diagramy}
-Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co jsi pod tímto, na první pohled ne zøejmým pojmem, pøedstavit. Mìjme mno¾inu teèek T rozmístìných náhodnì po papíru. Ke ka¾dému bodu nakreslíme okraje tak, aby vniklá plo¹ka obsahovala body, které jsou nejblí¾e právì té na¹í vybrané teèce. Samozøejmì "sousední" teèky budou mít tyto hranice spoleèné. Výsledkem na¹eho dlouhého sna¾ení pak bude právì Voroného diagram. V dal¹ích odstavcích se budeme zajímat o to, jak takový útvar správnì popsat, jak ho sestrojit a jaké datové struktury k tomu pou¾ít.
+Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co jsi pod tímto, na první pohled ne zøejmým pojmem, pøedstavit. Mìjme mno¾inu teèek $T$ rozmístìných náhodnì po papíru. Ke ka¾dému bodu nakreslíme okraje tak, aby vniklá plo¹ka obsahovala body, které jsou nejblí¾e právì té na¹í vybrané teèce. Samozøejmì "sousední" teèky budou mít tyto hranice spoleèné. Výsledkem na¹eho dlouhého sna¾ení pak bude právì Voroného diagram. V dal¹ích odstavcích se budeme zajímat o to, jak takový útvar správnì popsat, jak ho sestrojit a jaké datové struktury k tomu pou¾ít.
\s{Definice:} Voronoi diagram pro koneènou mno¾inu $M = \{m_1, \dots, m_n\} \in {\bb R}^2$ míst je systém mno¾in $1..M_n$ takových, ¾e pro v¹echny $i$ a $j$ a pro v¹echny $x \in M_i$ je vzdálenost $x$ a $m_i$ men¹í nebo rovna vzdálenosti $x$ a $m_j$ a zároveò sjednocení $M_i$ pøes v¹echna $i$ je celý prostor ${\bb R}^2$, neboli:
\s{Pozorování:}
\itemize\ibull
-\:Pro v¹echny $i$ je $M_i$ ohranièena konvexní lomenou èarou, tak¾e oblasti mají tvar konvexních mnohoúhelníkù, ale je mo¾né, ¾e jsou oteveøené do nekneèna.
+\:Pro v¹echny $i$ je $M_i$ ohranièena konvexní lomenou èarou, tak¾e oblasti mají tvar konvexních mnohoúhelníkù, ale je mo¾né, ¾e jsou otevøené do nekoneèna.
\:Pro ka¾dou hranu $h$ ve Voroného diagramu existuje $i$ a $j$ takové, ¾e kdy¾ $x \in H$, pak vzdálenost $d(x,m_i) = d(x,m_j)$.
Øekneme, ¾e vrchol je takové místo, kde se potkávají alespoò dvì hrany.
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