X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=9-geom%2F9-geom.tex;h=a46457aa2478e714e11e0ecc721ab0783b5a0320;hb=1b76f55dbcd7e4e4f104f9d855ecf698b2670593;hp=1dd9c0b6f45bcb5476f4a17e23b9aca3d626097e;hpb=d25f6d59986e343f18c42d48fa54b5a7fe6ff652;p=ads2.git diff --git a/9-geom/9-geom.tex b/9-geom/9-geom.tex index 1dd9c0b..a46457a 100644 --- a/9-geom/9-geom.tex +++ b/9-geom/9-geom.tex @@ -2,18 +2,17 @@ \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: @@ -21,10 +20,10 @@ Intuice n \: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.} @@ -32,14 +31,14 @@ Algoritmus funguje tak 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 . @@ -74,7 +73,7 @@ Set \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: @@ -84,7 +83,7 @@ Voron \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. @@ -137,18 +136,26 @@ Posledn 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} @@ -169,7 +176,12 @@ Posledn \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)$.