\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ì).
+\>Budeme se teï bavit o geometrických problémech v~rovinì. Vìt¹ina algoritmù,
+které zde uvedeme, má sice své obdoby i pro prostory vy¹¹í nebo ni¾¹í dimenze,
+ale jednorozmìrné pøípady 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ì 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øí, 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?!}
-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.
+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ì 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 v¹echny rybky?!}
-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ø.
+Neboli budeme øe¹it, jak nìjakou zadanou mno¾inu bodù v~rovinì obalit co
+nejkrat¹í uzavøenou køivkou, do které se je¹tì v¹echny body vejdou.
-\>Mo¾ná by se teï hodilo pøedvést názornì jak vypadají nejmen¹í konvexní obaly:
+Intuice nám napovídá ¾e výsledek bude nìjaký konvexní\foot{Mno¾ina bodù
+v~rovinì je konvexní, pokud platí, ¾e pro ka¾dé dva body této mno¾iny le¾í
+ú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ø. Tomuto mnohoulehníku se øíká {\I
+konvexní obal} dané mno¾iny.
+
+\>Mo¾ná by se teï hodilo pøedvést názornì, jak vypadají nejmen¹í konvexní
+obaly:
+
+\figure{ZakladniObaly.eps}{Základní obaly.}{3in}
\itemize\ibull
-\: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 4 bodù \dots to u¾ je slo¾itìj¹í
+
+\: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 trojúhleník s vrcholy v~tìchto bodech.
+
+\:Konvexní obal 4 bodù \dots to u¾ je slo¾itìj¹í\dots
+
\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.
-Jeden dobrý zpùsob jak tento konvexní obal sestrojit se nazývá {\I Zametání roviny.}
+Konvexní obaly 4 a více bodù, jak si mù¾eme v¹imnout, u¾ nejsou jednoznaèné.
+Pro $N$-prvkovou mno¾inu bude konvexní obal mnohoúhelník se tøemi a¾ $N$
+vrcholy.
-Algoritmus funguje tak ¾e si v~rovinì zvolíme nìjaký smìr, a v~tomto smìru zaèneme posouvat pøímku.
-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.
+Jeden dobrý zpùsob, jak tento konvexní obal sestrojit se nazývá {\I Zametání
+roviny.}
-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.
+Algoritmus funguje tak, ¾e si v~rovinì zvolíme nìjaký smìr, a v~tomto smìru
+zaèneme posouvat pøímku. Budeme takto potkávat body le¾ící v~na¹í mno¾inì.
+V~ka¾dém okam¾iku budeme chtít, aby body v~èásti, kterou jsme ji¾ zametli, u¾
+mìli spoèítaný konvexní obal. V¾dy kdy¾ pak zametací pøímkou narazíme na nový
+bod, u¾ si jen rozmyslíme, jak ho do konvexního obalu pøidat.
-Jde také vidìt ¾e bod s nejmen¹í a nejvìt¹í $X$-ovou souøadnicí bude le¾et v~konvexním obalu.
+BÚNO pøedpokládáme body v~obecné poloze, tedy takové, ¾e ¾ádné tøi nele¾í
+na~jedné pøímce. Dále také budeme pøedpokládat, ¾e budeme zametat ve smìru
+$x$-ové osy a ¾e v¹echny body mají rùznou $x$-ovou souøadnici.
+
+Je také vidìt, ¾e bod s nejmen¹í a nejvìt¹í $x$-ovou souøadnicí bude le¾et
+na~konvexním obalu.
+
+\s{My¹lenka algoritmu:}
-\s{Algoritmus:}
\algo
-\:Setøídíme body podle jejich $X$-ové souøadnice.
-\:Vezmem první tøi body a sestojí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 .
-\endalgo
-Ka¾dá iterace tedy bude probíhat tak, ¾e nìjaké body z pùvodního konvexního obalu pozapomínáme a pøidáme ná¹ nový bod.
-Aby se to lépe popisovalo, tak celý konvexní obal rozdìlíme na {\I horní obálku} a {\I dolní obálku.}
+\:Setøídíme body podle jejich $x$-ové souøadnice.
+
+\:Vezmeme 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.
-:: Obrazek obalek ::
+\::Pokud jej pøidat rovnou nemù¾eme, pak je potøeba nejdøíve nìjaké body
+odzadu odebrat a pak teprve pøipojit ná¹ nový bod. \endalgo
-Vidíme teï, ¾e dolní obálka je nìjaká lomená èára, která zatáèí doleva. Horní obálka zatáèí doprava.
-v~na¹em algoritmu si budeme obálky pamatovat jako seznamy vrcholù. Kdy¾ narazíme na nový vrchol tak
+Ka¾dá iterace tedy bude probíhat tak, ¾e nìjaké body z pùvodního konvexního
+obalu pozapomínáme a pøidáme nový bod. Aby se to lépe popisovalo, tak celý
+konvexní obal rozdìlíme na {\I horní obálku} a {\I dolní obálku.}
+
+\figure{HD-obalka.eps}{Obrázek obálek.}{3in}
+
+Vidíme teï, ¾e dolní obálka je nìjaká lomená èára, která zatáèí doleva. Horní
+obálka zatáèí doprava. V~na¹em algoritmu si budeme obálky pamatovat jako dva
+seznamy vrcholù. Kdy¾ pak v~algoritmu narazíme na nový bod, budeme zvlá¹»
+øe¹it jak to ovlivní horní obálku a jak ovlivní dolní. Je vidìt ¾e bod nejvíce
+vlevo a bod nejvíce vpravo le¾í v obou obálkách. Ostatní body buï le¾í jen
+v~jedné z obálek, nebo nele¾í v~¾ádné z nich (tedy nejsou souèástí konvexního
+obalu).
\s{Algoritmus:}
+
\algo
+
\:Setøídíme body podle souøadnice $x$, dostaneme mno¾inu bodù $b_1~-~b_n$.
-\:Spoèítáme konvexní obal ${b_1, b_2, b_3}$, z toho získáme horní a dolní obálku.
-\:Pro $b$ postupnì zpracováváme $b_3 - b_n$:
+\:Spoèítáme konvexní obal ${b_1, b_2, b_3}$, z toho získáme horní a dolní
+obálku\foot{Body $b_1$ a $b_3$ budou v obou obálkách. Bod $b_2$ bude v~horní
+obálce pokud le¾í nad pøímkou spojující $b_1$ a $b_3$, v~dolní obálce bude
+pokud le¾í pod pøímkou.}. \:Pro $b$ postupnì zpracováváme $b_3 - b_n$:
+
\::Pøepoèítáme Horní obálku:
-\:::Dokud $(\vert H\vert \geq 2)$ a úhel $(H[-2], H[-1], b)$ je orientovaný doleva:
-\::::Odebereme poslední prvek z obálky.
+
+\:::Dokud $(\vert H\vert \geq 2)$ a úhel $(H[-2], H[-1], b)$ je orientovaný
+doleva: \::::Odebereme poslední prvek z obálky.
+
\:::Pøidáme do obálky nový vrchol.
+
\::Pøepoèítáme dolní obálku:
-\:::Dokud $(\vert D\vert \geq 2)$ a úhel $(D[-2], D[-1], b)$ je orientovaný doprava:
-\::::Odebereme poslední prvek z obálky.
+
+\:::Dokud $(\vert D\vert \geq 2)$ a úhel $(D[-2], D[-1], b)$ je orientovaný
+doprava: \::::Odebereme poslední prvek z obálky.
+
\:::Pøidáme do obálky nový vrchol.
+
\endalgo
-Setøídit body podle $X$-ové souøadnice a sestrojit konvexní obal prvních tøech bodù stihneme v~èase $\O(n \log n)$. Zbytek pak u¾ udìláme dokonce v~èase lineárním $\O(n)$. Tedy
+Setøídit body podle $x$-ové souøadnice a sestrojit konvexní obal prvních tøech
+bodù stihneme v~èase $\O(n \log n)$. Zbytek pak u¾ udìláme dokonce v~èase
+lineárním $\O(n)$\foot{V této èásti u¾ jen do obálek pøidáváme a odebíráme
+body.Pøidáváme jich $N$. A odebrat jich mù¾eme maximálnì tolik kolik jsme jich
+pøidali. Tedy zase maximálnì~$N$.}. Platí tedy:
\s{Vìta:} Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$.
+\>Na¹i lední medvìdi se tedy ji¾ nauèili, jak si efektivnì obstarat potravu a
+mohly se pustit do øe¹ení dal¹ího velmi dùle¾itého problému. Pojïme se na nìj
+podívat s nimi. \>A o co ¾e to pùjde?
+
+{\I Lední medvìdi nejsou na antarktidì sami, kromì nich tam taky bydlí
+kamarádi eskymáci ve svých iglù. Medvìdi by si teï rádi udìlali mapu, podle
+které by hned poznali, ke kterému ekymákovi to mají nejblí¾e na náv¹»evu.}
+
+My tuhle medvìdí mapu od teï budeme nazývat {\I Voroneho diagramem}.
+
\h{Voroného diagramy}
-Pøed tím, ne¾ vás vystra¹ím nìjakou definicí, si øekneme, co si 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ì \uv{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:} {\I Voroného diagram} pro koneènou mno¾inu $M = \{m_1, \dots,
+m_n\} \in {\bb R}^2$ míst je systém mno¾in $O_1,\dots,O_n$ takových, ¾e pro
+v¹echna $i$ a $j$ a pro v¹echna $x \in M_i$ je vzdálenost $x$ od $m_i$ men¹í
+nebo rovna vzdálenosti $x$ od $m_j$ a zároveò sjednocení $O_i$ pøes v¹echna
+$i$ je celý prostor ${\bb R}^2$, neboli:
+
+$$d(x,m_i) \leq d(x,m_j) \wedge {\bigcup}_i O_i = {\bb R}^2.$$
+
+Jednoduchý Voroného diagram:
-\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:
+\figure{voroneho2.eps}{Voroneho diagramu pro dvì místa.}{3in}
-$$d(x,m_i) \leq d(x,m_j) \wedge {\bigcup}_i M_i = {\bb R}^2.$$
+Voroného diagram se tedy skládá z nìjakých míst, oblastí a hran, které ty
+oblasti oddìlují.
-Voroného diagram se tedy skládá z nìjakých bodù, oblastí a hran, které ty oblasti oddìlují.
+\figure{voronoi.eps}{Èásti Voroneho diagramu.}{2in}
+
+\s{Definice:} Øekneme, ¾e {\I hrana} $H$ je taková mno¾ina bodù, ¾e pro ka¾dý
+bod $x \in H$ platí, ¾e existují dvì místa $m_i$ a $m_j$, od kterých má bod
+$x$ stejnou vzdálenost. Tyto dvì místa jsou pro v¹echny body $x$ stejná a
+platí, ¾e v¹echny ostatní místa mají od ka¾dého bodu $x$ del¹í vzdálenost.
+
+\s{Definice:} Øekneme, ¾e {\I vrchol} je takový bod, kde se potkávají alespoò
+dvì hrany.
\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 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.
+\:Voroneho diagramem pro dvì místa jsou dvì poloroviny odìlené takovou pøímkou,
+ ¾e ka¾dý bod pøímky je stejnì vzdálený od obou míst. \:Ka¾dá mno¾ina $M_i$ je
+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 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)$. \:Pro ka¾dý vrchol $v$ Voroného diagramu
+existují alespoò tøi místa le¾ící na kru¾nici se støedem $v$.
-\:Pro ka¾dý vrchol $v$ Voroného diagramu existují alespoò tøi místa le¾ící
-na kru¾nici se støedem $v$.
\figure{body.eps}{Body na kru¾nici.}{3in}
-\:Poèet vrcholù a hran je lineární.
-\:Poèet krajních oblastí je tak velký, jak velký je konvexní obal té zadané mno¾iny. (je to dobré vìdìt, ale asi to nebudeme potøebovat)
+
+\:Poèet vrcholù a hran je lineární k poètu míst\foot{Voroneho diagram si lze
+pøedstavit jako graf, kde místa Voroneho diagramu odpovídají stìnám, vrcholy
+diagramu vrcholùm a hrany odpovídají hranám grafu. Pokud si teï nìkam mimo
+graf pøidáme je¹tì jeden vrchol a v¹echny pøímky vedoucí do nekoneèna navedeme
+do toho bodu, vidíme, ¾e ná¹ graf je roviný. Pro roviný graf platí Eulerova
+formule a z ní u¾ plyne ¾e na¹e linearita.}. \:Poèet krajních oblastí je tak
+velký, jak velký je konvexní obal té zadané mno¾iny. (Je to dobré vìdìt, ale
+asi to nebudeme potøebovat.)
+
\endlist
-Pojïme teï vymyslet, jak takový diagram utøídit. Mohli bychom zkonstruovat v¹echny dìlící pøímky a poslepovat je, ale vznikl by nám kvadratický algoritmus a to nám nemù¾e staèit.
-
-Mluvili jsme o zametání roviny a tak bychom tento trik mohli vyu¾ít právì pøi
-øe¹ení na¹eho problému. Ov¹em tentokrát má zametání jeden podstatný háèek. Kdy¾
-si vezmeme nìjakou zametací pøímku a pojedeme s ní od shora dolù, tak nad ní
-máme u¾ nìjakou zkonstruovanou èást diagramu a kdy¾ narazíme na dal¹í bod, tak
-se nám mù¾e právì tato èást pomìrnì slo¾itì zmìnit. Pomù¾eme si malým trikem.
-Nebudeme pova¾ovat ten diagram za uplnì hotový, ale pro ka¾dý bod nad pøímkou
-mno¾inu v¹ech bodù, které mají blí¾e k tomu pøíslu¹nému bodu ne¾ k té pøímce.
-To tvoøí nìjakou parabolu. Tak¾e v této oblasti u¾ je bezpeèno, v¹echno co jsme
-spoèítali uvnitø této paraboly nám u¾ nikdo nepokazí (ani nevylep¹í). Vezmeme si
-tedy dolní obálku tìchto parabol.
+Pojïme teï vymyslet, jak takový diagram vyrobit. Mohli bychom zkonstruovat
+v¹echny dìlící pøímky a poslepovat je, ale vznikl by nám kvadratický
+algoritmus a to nám nemù¾e staèit.
+
+Mluvili jsme o zametání roviny, a tak bychom tento trik mohli vyu¾ít právì pøi
+øe¹ení na¹eho problému. Ov¹em tentokrát má zametání jeden podstatný háèek.
+Kdy¾ si vezmeme nìjakou zametací pøímku a pojedeme s ní shora dolù, tak nad ní
+máme nìjakou u¾ zkonstruovanou èást diagramu a kdy¾ narazíme na dal¹í bod, tak
+se nám mù¾e právì tato èást diagramu pomìrnì slo¾itì zmìnit. Pomù¾eme si malým
+trikem. Nebudeme pova¾ovat za hotovou celou oblast nad zametací pøímkou, ale
+jen takové body, které mají blí¾e k místùm ($m_i$) ne¾ k zametací pøímce. Tak
+dostaneme nìjakou posloupnost (mno¾inu) parabol. V¹echno, co jsme spoèítali
+uvnitø této oblasti nám u¾ nikdo nepokazí (ani nevylep¹í), je tam bezpeèno.
+Vezmeme si tedy dolní obálku tìchto parabol, budeme jí øíkat {\I pobøe¾í}.
+
\figure{pobrezi.eps}{Pobøe¾ní linie.}{3in}
-Pobøe¾í je nìjaká posloupnost parabolických obloukù s tím, ¾e nejlevìj¹í a
-nejpravìj¹í jdou do nekoneèna.
-
-Kdykoliv tedy narazíme na nìjaký bod, tak nám mu¾e ovlivnit u¾ jen tu èást diagramu
-pod pobøe¾ím. Dostáváme se tedy k tomu, co se dìje, kdy¾ hýbeme zametací pøímkou.
-Pakli¾e nenará¾íme na ¾ádné body, tak se v podstatì nedìje nic pøíli¹ zajímavého.
-Zajímavá situace nastává a¾ tehdy, narazímeli na dal¹í bod. V tom okam¾iku vzniká
-nová parabola. V tuto chvíli je znaènì degenerovaná. Je to toti¾ vlastnì zatím jen
-polopøímka kolmá na na¹i øídící pøímku. S dal¹ím pohybem se zaène parabola rozevírat.
-V¹imnìme si, ¾e prùnik té na¹í pøímky a pobøe¾í je vlastnì vrchol ve Voroného diagramu.
-Mù¾e nastat je¹tì jeden problém. Nìjaká parabola se mù¾e natolik rozevøít, ¾e pohltí
-jiné.
-
-Shrneme-li na¹e úvahy, mù¾ou se dít celkem tøi vìci. Jedna z nich je posun pøímky.
-To se vlastnì dìje poøád. Nemìní se nám rif pobøe¾í a prùseèíky parabol nám kreslí
-hrany. To mù¾eme poèítat najednou. Navíc nejen ¾e bychom mohli s pøímkou skoèít
-o nìjaké epsilon, ale mi dokonce mù¾eme skoèit o poøádný kus a prostì pouze dopoèítat,
-jak se nám zmìnilo pobøe¾í a co se nám vykreslilo.
-
-Pokud tedy narazíme na bod, tak musíme najít místo, kde to na¹e pobøe¾í rozetnou
-a kam vklínit dal¹í výbì¾ek (parabolu). Takovéto události budeme øíkat místní událost.
-Pokud se pohybujeme v obecné poloze, tak se nám nestane, ¾e bychom narazili na prùseèík.
-\figure{mistni.eps}{Místní událost.}{3in}
-
-Poslední situace, která tedy mù¾e nastat je, ¾e nám nìjaký parabola schová za jiné.
-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á. 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.
+
+Pobøe¾í je tedy nìjaká posloupnost parabolických obloukù s tím, ¾e nejlevìj¹í
+a nejpravìj¹í jdou do nekoneèna. Prùseèíky tìchto obloukù vykreslují hrany
+diagramu. Proè? Odpovìï na tuto otázku není tì¾ká, staèí vyjít z definice
+paraboly tak, jak jí zde pou¾íváme. Nebo-li je to mno¾ina bodù, která je od
+ohniska (pro nás místa) stejnì vzdálená jako od pøímky (øídící). A tedy prùnik
+dvou parabol je místo, které je stejnì vzdálené od obou ohnisek, co¾ je
+vlastnì definice bodu le¾ícího na nìjaké hranì.
+
+Kdykoliv v prùbìhu zametání narazíme na nìjaký bod, mù¾e nám ovlivnit u¾ jen
+èást diagramu pod pobøe¾ím. Dostáváme se tedy k tomu, co se dìje, kdy¾ hýbeme
+zametací pøímkou. Pakli¾e nenará¾íme na ¾ádné body, tak se v podstatì nedìje
+nic zajímavého. Zajímavá situace nastává a¾ tehdy, narazíme-li na dal¹í bod.
+V~tom okam¾iku vzniká nová parabola. V tuto chvíli je znaènì degenerovaná. Je
+to toti¾ zatím jen polopøímka kolmá na zametací pøímku. S dal¹ím pohybem se
+zaène parabola rozevírat. V¹imnìme si, ¾e prùnik oné pøímky a pobøe¾í je
+vlastnì vrchol Voroného diagramu.
+
+Mù¾e nastat je¹tì jeden problém. Nìjaká parabola se mù¾e natolik rozevøít, ¾e
+pohltí jiné a ty zmizí z pobøe¾ní linie. V takovém pøípadì, se nám ale
+netriviálnì zmìní vzhled pobøe¾í, a proto se této situaci budeme muset více
+vìnovat.
+
+Shrneme-li na¹e úvahy, mohou se dít celkem tøi vìci. Jedna z nich je posun
+pøímky. To se vlastnì dìje poøád. Pobøe¾í se témìø nemìní a prùseèíky parabol
+nám kreslí hrany. To mù¾eme poèítat najednou. Navíc nejen ¾e bychom mohli s
+pøímkou skoèit o nìjaké epsilon, ale my dokonce mù¾eme skoèit o poøádný kus a
+prostì pouze dopoèítat, jak se pobøe¾í zmìnilo a co se vykreslilo. Dùle¾itým
+místùm, kde se budeme zastavovat, budeme øíkat {\I události}.
+
+\>{\I Místní událost}
+
+Pokud narazíme na bod, musíme najít místo, kde pobøe¾í rozetnou a kam vklínit
+dal¹í výbì¾ek (parabolu). Takovéto události budeme øíkat místní událost.
+
+\figure{mistni.eps}{\vbox{\hsize=0.6\hsize\leftskip=0pt plus
+0.3\hsize\rightskip=\leftskip\parfillskip=0pt \>Místní událost -- èervená
+kolmice je novì vznikající parabola, pøi postupu zametací pøímky dále se bude
+rozevírat a vytvoøí dal¹í parabolu.}}{3in}
+
+\>{\I Kru¾nicová událost}
+
+Poslední situace, která mù¾e nastat, je, ¾e se nìjaká parabola schová za jiné.
+Kouknìme se na první obrázek ní¾e, fialový bod je støed kru¾nice opsané
+trojùhelníku tvoøenému tøemi místy. Jak víme, ten le¾í na osách stran takového
+trojùhelníku. Po tìchto osách se v¹ak budou i pohybovat prùseèíky parabol a s
+posunováním øídící pøímky se pak dostanou v¹echny tøi do støedu této kru¾nice.
+Stane se to pravì tehdy, kdy¾ se zametací pøímka dotkne kru¾nice zespodu. Je
+mo¾né nahlédnout, ¾e pøi postupu dále se pak dvì krajní paraboly roz¹íøí
+natolik, ¾e prostøední pohltí a ta zanikne. Takto vzniklé události budeme
+øíkat 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í a druhý právì kru¾nicovou událost. Mimo jiné
+by tedy z obrázkù mìlo být patrné, ¾e kru¾nicové události jsou urèeny
+trojicemi sousedních obloukù v pobøe¾í.
+
\figure{kruznicova.eps}{Pøed kru¾nicovou událostí.}{3in}
-\figure{kruznicovakonec.eps}{Kru¾nicová 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).
+
+Dále bude zapotøebí udr¾ovat si 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}, jinak øeèeno pøidat a odebrat oblouk a najít
+oblouk podle x-sové souøadnice nebo-li oblouk do kterého jsme se trefili pøi
+místní události. Navíc budeme potøebovat vyhledávací strom nad prùseèíky s
+implicitní reprezentací, co¾ znamená, ¾e si ve vrcholech nebudeme pamatovat
+pøímo souøadnice prùseèíkù, ale jen instrukci, jak je spoèítat. Tak¾e jakkoli
+se mìní poloha prùseèíkù, tak struktura stromu zùstává stejná.
-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).$
+S haldou událostí lze pracovat s logaritmickou èasovou slo¾itostí na operaci
+a ve stejném èase doká¾eme pracovat s pobøe¾ní linií. Kdy¾ si pobøe¾í je¹tì
+reprezentujeme zvlá¹» jako seznam tak Insert a Delete budou v konstatním èase
+a operace se stromem pak $\O(\log n)$.
Poslední datovou strukturou bude samotný diagram, reprezentovaný grafem se
souøadnicemi a vazbami hran na prùseèík.
-
\s{Fortunùv~algoritmus}
+
\algo
+
\:Pøipravíme si haldu $H$ a vlo¾íme do ní v¹echny místní události.
+
\:Pøipravíme pobøe¾ní linii $P \leftarrow 0$.
+
\:Dokud existuje $h \leftarrow DeleteMin(H)$:
+
\::Je-li na øadì místní událost:
+
\:::Najdeme prùseèík s $P(FindX(P))$.
+
\:::Vlo¾íme do $P$ novou parabolu.
+
\:::Poznamenáme do $D$ vznik hran.
+
\:::Pøepoèítáme kru¾nicové události.
+
\::Je-li na øadì kru¾nicová událost:
+
\:::Sma¾eme oblouk z $P$.
+
\:::Poznamenáme vznik a zánik do $D$.
+
\:::Pøepoèítáme kru¾nicové události.
-\endalgo
+\endalgo
\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$ (na ka¾dé místo narazíme právì jednou).
+Poèet kru¾nicových událostí není vìt¹í ne¾ $n$, proto¾e kru¾nicová událost sma¾e
+parabolu a ty vznikají jen pøi místních událostech, tak¾e kru¾nicových událostí
+není více ne¾ místních. Speciálnì z toho plyne, ¾e velikost pobøe¾ní linie je
+v¾dy lineární, proto¾e s ka¾dou místní událostí pøibudou dva úseky do pobøe¾ní
+linie, tak¾e velikost pobøe¾ní linie je maximálnì $2n$. Velikost haldy je pak
+také $2n$, tak¾e pak operace urèitì zvládneme v èase $\O(\log n)$. Jeliko¾
+diagram je lineárnì velký tak i jeho struktura je lineárnì velká. Operace se
+strukturami nás stojí nejvíce $\O(\log n)$. Tak¾e místní i kru¾nicové události
+zvládneme v èase $\O(\log n)$ na jednu na konstantním poètu struktur. Halda má
+velikost $2n$, tak¾e maximálnì provedeme $\O(2n\log n)$ operací.
+Celý algoritmus potøebuje na~inicializaci maximálnì $\O(n \log n)$ (i kdybychom
+ji dìlali neefektivnì) a $\O(2n\log n)$ výpoèet.
Pokud tedy shrneme v¹echny na¹e odhady, pak èasová slo¾itost algoritmu je
$\O(n \log n)$ a prostorová $\O(n)$.
-
\bye
-
-------------------
1) Pøipravíme si haldu $H$ a vlo¾íme do ní v¹echny místní události.
-2) pøipravíme pobøe¾ní linii P <- 0 } O(n*log n)
-3) pøipraváme reprezentaci diagramu D /
+
+2) pøipravíme pobøe¾ní linii P <- 0 } O(n\log n)
+
+3) pøipraváme reprezentaci diagramu D /
+
4) dokud existuje h <- DeleteMin(H)
-5) je-li na øadì místní událost: ----
- a) najdeme prùseèík s P(FindX(P)) \
- b) vlo¾íme do P novou parabolu \
- c) poznamenáme do D vznik hran } O(log n)
- d) pøepoèítáme kru¾nicové události / } <= 2n
-6) je-li na øadì kru¾nicová událost:
- a) sma¾eme oblouk z P \
- b) poznamenáme vznik a zánik do D } O(log n)
- c) pøepoèítáme kru¾nicové události / ----
+5) je-li na øadì místní událost: ----
+
+a) najdeme prùseèík s P(FindX(P)) \
+
+b) vlo¾íme do P novou parabolu \
+
+c) poznamenáme do D vznik hran } O(\log n)
+
+d) pøepoèítáme kru¾nicové události / } <= 2n
+
+6) je-li na øadì kru¾nicová událost:
+
+a) sma¾eme oblouk z P \
+b) poznamenáme vznik a zánik do D } O(\log n)
+c) pøepoèítáme kru¾nicové události / ----
\bye
projects / ads2.git / blobdiff