X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=9-geom%2F9-geom.tex;h=a46457aa2478e714e11e0ecc721ab0783b5a0320;hb=1b76f55dbcd7e4e4f104f9d855ecf698b2670593;hp=6ca2f6049136f83d40c3857dfc4fd8a9f8bd123b;hpb=be3502110aea505a6f8aa610374f58670c325524;p=ads2.git diff --git a/9-geom/9-geom.tex b/9-geom/9-geom.tex index 6ca2f60..a46457a 100644 --- a/9-geom/9-geom.tex +++ b/9-geom/9-geom.tex @@ -8,11 +8,11 @@ Budeme se tedy zab \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?!} +{\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: @@ -20,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.} @@ -31,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 . @@ -73,7 +73,7 @@ Set \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ì "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: @@ -83,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 nekoneè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.