\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 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ì 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 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é se je¹tì v¹echny body vejdou.
-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í, 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.
-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ø.
+\>Mo¾ná by se teï hodilo pøedvést názornì, jak vypadají nejmen¹í konvexní obaly:
-\>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.
+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.
-Jeden dobrý zpùsob jak tento konvexní obal sestrojit se nazývá {\I Zametání roviny.}
+Jeden dobrý zpùsob, jak tento konvexní obal sestrojit se nazývá {\I Zametání roviny.}
-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.
+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.
-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 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.
-Jde také vidìt ¾e bod s nejmen¹í a nejvìt¹í $X$-ovou souøadnicí bude le¾et v~konvexním obalu.
+Je také vidìt, ¾e bod s nejmen¹í a nejvìt¹í $x$-ovou souøadnicí bude le¾et na~konvexním obalu.
-\s{Algoritmus:}
+\s{My¹lenka algoritmu:}
\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:
+\: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.
-\::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 .
+\::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
-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.}
+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.}
-:: Obrazek obalek ::
+\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 seznamy vrcholù. Kdy¾ narazíme na nový vrchol tak
+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.
+\: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:
\:::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)$.
-\h{Voroného diagramy}
+\>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.}
-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.
+My tuhle medvìdí mapu od teï budeme nazývat {\I Voroneho diagramem}.
-\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:
-
-$$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 bodù, oblastí a hran, které ty oblasti oddìlují.
+\h{Voroného diagramy}
-\s{Pozorování:}
+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.$$
+
+Voroného diagram se tedy skládá z nìjakých míst, oblastí a hran, které ty oblasti oddìlují.
+
+\s{Definice:} Øekneme, ¾e {\I hrana} $H$ je taková mno¾ina bodù, ¾e pro ka¾dý bod $x \in H$
+platí.
+\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 nekneèna.
+\: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)$.
-
-Øekneme, ¾e vrchol je takové místo, kde se potkávají alespoò dvì hrany.
-
\: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 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.
+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
+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.
+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
+Pobøe¾í je tedy 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
+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 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.
+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é.
+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}.
-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.
+Místní událost
-Pokud tedy narazíme na bod, tak musíme najít místo, kde to na¹e pobøe¾í rozetnou
+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.
-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}
+Pokud se pohybujeme v obecné poloze, nestane se nám, ¾e bychom narazili na prùseèík.
+\figure{mistni.eps}{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}
-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á.
-\figure{kruznicova.eps}{Kru¾nicová událost.}{3in}
+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 le¾í na v¹ech tøech parabolách.
+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 zespodu.
+Tato kru¾nice je urèena právì tìmito tøemi ohnisky. Vzniklé události budeme øíkat kru¾nicová.
+Z obrázku by tedy mìlo být patrné (alespoò èásteènì), ¾e kru¾nicové události
+jsou urèeny trojicemi sousedních obloukù v pobøe¾í.
+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.
+\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í udr¾ovat si pobøe¾ní linii, nebo-li 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{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$.
+\: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.
+\:::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
+
+\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$, proto¾e kru¾nicové události odpovídají vrcholùm, a proto tìch, kterých se
+ doopravdy provedou je pouze $\O(n)$, 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 sousedních 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.
-\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.
-
-Pokud tedy shrneme v¹echny na¹e odhady, pak èasová slo¾itost algoritmu je
-$\O(n \log n)$ a prostorová $\O(n)$.
+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 /
+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)) \
projects / ads2.git / blobdiff