From cb2d113a0fd07ba29a8170092f34210afa9fa483 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 10 Jan 2010 21:01:37 +0100 Subject: [PATCH 1/1] Doplnena 2. geometricka prednaska. --- 8-geom2/8-geom2.mp | 80 +++++++++++- 8-geom2/8-geom2.tex | 164 ++++++++++++++++--------- 8-geom2/8-geom2_1_usecky.eps | 2 +- 8-geom2/8-geom2_2_polorovina.eps | 29 ++++- 8-geom2/8-geom2_3_voroneho_diagram.eps | 72 +++++------ 8-geom2/lib.mp | 2 + 6 files changed, 246 insertions(+), 103 deletions(-) diff --git a/8-geom2/8-geom2.mp b/8-geom2/8-geom2.mp index 3720dc0..5a44396 100644 --- a/8-geom2/8-geom2.mp +++ b/8-geom2/8-geom2.mp @@ -27,18 +27,26 @@ beginfig(2); fill p--reverse(p shifted (A-0.8[A,B]))--cycle withcolor 0.8white; %fill p{dir (an+180)}..-0.35[A,B]..{dir an}cycle withcolor 0.8white; draw p withpen boldpen; + + pair C; C := point(0.9) of p; + drawarrow from(C,an+180,0.1cm)--from(C,an+180,1cm) withpen boldpen; + C := point(0.1) of p; + drawarrow from(C,an+180,0.1cm)--from(C,an+180,1cm) withpen boldpen; + label.rt(btex $p$ etex, point(0.15) of p); draw A--B dashed evenly; drawemptyvertex(A); drawemptyvertex(B); label.llft(btex $a$ etex, A); label.urt(btex $b$ etex, B); + label(btex $B_a$ etex, A+2(-0.1cm,0.5cm)); + label(btex $B_b$ etex, B+2(-0.1cm,0.5cm)); endfig; figtag("voroneho_diagram"); beginfig(3); u := 1.35cm; pair A[],B[]; - A0 := origin; A1 := (-u,-u); A2 := (1.3u,-u); A3 := (1.5u,0.7u); A4 := (0.6u,0.8u); A5 := (0.2u,1.9u); A6 := (-1.3u,1u); + A0 := origin; A1 := (-u,-u); A2 := (1.3u,-u); A3 := (1.50821u,0.7u); A4 := (0.6u,0.8u); A5 := (0.2u,1.9u); A6 := (-1.3u,1u); def osa(expr a, b, an,l) = from(.5[a,b], angle(b-a)+an, l) enddef; vardef prusecik_os(expr p,q,r) = save b; pair b; @@ -47,19 +55,83 @@ beginfig(3); b enddef; B[0] := prusecik_os(A0,A1,A2); B[1] := prusecik_os(A0,A1,A6); B[2] := prusecik_os(A0,A4,A6); B[3] := prusecik_os(A4,A5,A6); - B[4] := prusecik_os(A3,A4,A5); B[5] := prusecik_os(A0,A3,A4); B[6] := prusecik_os(A0,A2,A3); + B[4] := prusecik_os(A3,A4,A5); B[5] := prusecik_os(A0,A3,A4); B[6] := prusecik_os(A0,A2,A4); draw osa(A1,A2,-90,2cm)--B[0]--B[1]--osa(A1,A6,90,1.3cm) withpen boldpen; draw B[1]--B[2]--B[3]--osa(A6,A5,90,2cm) withpen boldpen; draw B[3]--B[4]--osa(A3,A5,-90,2.7cm) withpen boldpen; draw B[4]--B[5]--B[2] withpen boldpen; draw B[5]--B[6]--osa(A2,A3,-90,1.3cm) withpen boldpen; draw B[6]--B[0] withpen boldpen; - + draw A0--A1--A2--A0--A6--A1 dashed evenly; - draw A6--A5--A4--A0--A3--A2 dashed evenly; + draw A6--A5--A4--A0 dashed evenly; draw A3--A2 dashed evenly; draw A3--A5 dashed evenly; draw A6--A4--A3 dashed evenly; for i:=0 upto 6: draw vertex(B[i]); endfor for i:=0 upto 6: drawemptyvertex(A[i]); endfor endfig; + +figtag("pasy_mnohouhelniku"); +beginfig(4); + u := 1.35cm; + pair A[],B[]; + A0 := origin; A1 := (-u,-u); A2 := (1.3u,-u); A3 := (1.50821u,0.7u); A4 := (0.6u,0.8u); A5 := (0.2u,1.9u); A6 := (-1.3u,1u); + def osa(expr a, b, an,l) = from(.5[a,b], angle(b-a)+an, l) enddef; + vardef prusecik_os(expr p,q,r) = + save b; pair b; + b = whatever[osa(p,q, 90,1cm), osa(p,q,-90,1cm)]; + b = whatever[osa(q,r, 90,1cm), osa(q,r,-90,1cm)]; + b + enddef; + def drawline(expr p) = draw ((-2.3u,p)--(2.5u,p)) cutbefore (D0--D1) cutafter (D2--D3) enddef; + B[0] := prusecik_os(A0,A1,A2); B[1] := prusecik_os(A0,A1,A6); B[2] := prusecik_os(A0,A4,A6); B[3] := prusecik_os(A4,A5,A6); + B[4] := prusecik_os(A3,A4,A5); B[5] := prusecik_os(A0,A3,A4); B[6] := prusecik_os(A0,A2,A4); + + pair C; C := origin; for i:=0 upto 6: C := C + B[i]; endfor C := C/6; + pair D[]; + D0 := C+(-2.25,2.25)*u; D1 := C+(-2.25,-2.25)*u; D2 := C+(2.25,-2.25)*u; D3 := C+(2.25,2.25)*u; + + draw B[0]--B[1]--B[2]--B[3]--B[4]--B[5]--B[6]--B[0] withpen boldpen; + draw B[5]--B[2] withpen boldpen; + pair E; E := 0.6[B0,B4]; + drawline(ypart(E)); + drawline(ypart(E)) cutbefore (B2--B5) cutafter (B4--B5) dashed evenly withpen bolderpen; + drawemptyvertex(E); + + for i:=0 upto 6: drawline(ypart(B[i])) dashed evenly; endfor + for i:=0 upto 6: draw vertex(B[i]); endfor +endfig; + +figtag("upravy_stromu"); +beginfig(5); + u := 1cm; + draw (0,0.1u)--(2.05u,-2.05u)--(-2.05u,-2.05u)--cycle; + pair A[]; A0 := from(origin,-90,0.1u); A1 := from(A0, -70, 0.5u); A2 := from(A1, -110, 0.5u); A3 := from(A2, -80, 0.5u); A4 := from(A3, -120, 0.45u); + path p; p := createpath(A0--A1--A2--A3--A4); + path q; q := (p scaled 0.93 shifted (-0.15u,-0.15u))--(-1.85u,-1.95u)--cycle; fill q withcolor 0.8white; draw q; + q := (p scaled 0.93 shifted (0.15u,-0.15u))--(1.85u,-1.95u)--cycle; fill q withcolor 0.8white; draw q; + p := createpath(A0--from(A0,-110,0.1u)--A1--A2--A3--A4); draw p withpen boldpen; +endfig; + +figtag("rychla_perzistence"); +beginfig(6); + u := 1cm; + def drawtable(expr p, lab, sa, sb) = + draw centersquare xscaled 2u yscaled (2u/3) shifted (p+(0,u/3)); + draw centersquare xscaled 2u yscaled (2u/3) shifted (p-(0,u/3)); + label(sa, p+(0,u/3)); + label(sb, p-(0,u/3)); + label.bot(lab, p-(0,2u/3)); + enddef; + + pair A[]; + for i:=0 upto 2: A[i] := (0,2u) rotated 120i; endfor + drawtable(A1, btex $v$ etex, btex verze 2 etex, btex verze 1 etex); + drawtable(A2, btex $v'$ etex, btex verze 3 etex, ""); + drawtable(A0, btex $u$ etex, btex verze 2 etex, btex verze 1 etex); + + drawarrow from(A[2]+(0,u/3), 180, 7u/6)--from(A[1]+(0,u/3), 0, 7u/6); + drawarrow from(A[0]+(0,-u/3), 180, 7u/6)..{dir -90}from(A[1]+(-3u/4,2u/3), 90, u/6); + drawarrow from(A[0]+(0,u/3), 0, 7u/6)..{dir -90}from(A[2]+(3u/4,2u/3), 90, u/6); +endfig; end diff --git a/8-geom2/8-geom2.tex b/8-geom2/8-geom2.tex index 1e2e593..3924f4d 100644 --- a/8-geom2/8-geom2.tex +++ b/8-geom2/8-geom2.tex @@ -2,8 +2,8 @@ \prednaska{8}{Geometrie vrací úder}{(sepsal Pavel Klavík)} -\>Kdy¾ s geometrickými problémy poøádnì nezametete, ony vám to vrátí! Ale kdy¾ u¾ zametat, tak urèitì ne pod koberec a místo smetáku si na nì vezmìte -pøímku. V této pøedná¹ce nás spolu s dvìma geometrickými problémy samozøejmì èeká pokraèování pohádky o ledních medvìdech. +\>Kdy¾ s geometrickými problémy poøádnì nezametete, ony vám to vrátí! Ale kdy¾ u¾ zametat, tak urèitì ne pod koberec a místo smetáku pou¾ijte pøímku. +V této pøedná¹ce nás spolu s dvìma geometrickými problémy samozøejmì èeká pokraèování pohádky o ledních medvìdech. {\I Medvìdi vyøe¹ili rybí problém a hlad je ji¾ netrápí. Av¹ak na severu ne¾ijí sami, za sousedy mají Eskymáky. Proto¾e je rozhodnì lep¹í se sousedy dobøe vycházet, jsou medvìdi a Eskymáci velcí pøátelé. Skoro ka¾dý se svými pøáteli rád schází. Av¹ak to je musí nejprve nalézt~\dots} @@ -23,9 +23,9 @@ Pro zjednodu \centerline{Problém Eskymákù: Kde v¹ude se køí¾í medvìdí trasy?} \bigskip -Pro $n$ úseèek mù¾eme mít a¾ $\Omega(n^2)$ prùseèíkù.\foot{Zkuste takový pøíklad zkonstruovat.} Tedy optimální slo¾itosti by dosáhl i algoritmus, který -by pro ka¾dou dvojici úseèek testoval, zda se protínají. Èasto se slo¾itost algoritmu posuzuje i vzhledem k velikosti výstupu $p$. Typické rozmístìní -úseèek mívá toti¾ prùseèíkù spí¹e po málu. Pro tento pøípad si uká¾eme podstatnì rychlej¹í algoritmus. +Pro $n$ úseèek mù¾e existovat a¾ $\Omega(n^2)$ prùseèíkù.\foot{Zkuste takový pøíklad zkonstruovat.} Tedy optimální slo¾itosti by dosáhl i algoritmus, +který by pro ka¾dou dvojici úseèek testoval, zda se protínají. Èasovou slo¾itost algoritmu v¹ak posuzujeme i vzhledem k velikosti výstupu $p$. Typické +rozmístìní úseèek mívá toti¾ prùseèíkù spí¹e pomálu. Pro tento pøípad si uká¾eme podstatnì rychlej¹í algoritmus. Pro jednodu¹¹í popis pøedpokládejme, ¾e úseèky le¾í v obecné poloze. To znamená, ¾e ¾ádné tøi úseèky se neprotínají v jednom bodì a prùnikem ka¾dých dvou úseèek je nejvý¹e jeden bod. Navíc pøedpokládejme, ¾e krajní bod ¾ádné úseèky nele¾í na jiné úseèce a také neexistují vodorovné úseèky. Na závìr si @@ -37,7 +37,7 @@ nov Zajímavé události jsou {\I zaèátky úseèek}, {\I konce úseèek} a {\I prùseèíky úseèek}. Po utøídìní známe pro první dva typy událostí poøadí, v jakém se objeví. Výskyty prùseèíkù budeme poèítat prùbì¾nì, jinak bychom celý problém nemuseli øe¹it. -V ka¾dém kroku si pamatujeme prùøez $P$ -- posloupnost úseèek aktuálnì protnutých zametací pøímkou. Tyto úseèky máme utøídìné zleva doprava. Navíc si +V ka¾dém kroku si pamatujeme {\I prùøez} $P$ -- posloupnost úseèek aktuálnì protnutých zametací pøímkou. Tyto úseèky máme utøídìné zleva doprava. Navíc si udr¾ujeme kalendáø $K$ budoucích událostí. Z hlediska prùseèíkù budeme na úseèky nahlí¾et jako na polopøímky. Pro sousední dvojice úseèek si udr¾ujeme, zda se jejich smìry nìkde protnou. Algoritmus pro hledání prùnikù úseèek funguje následovnì: @@ -55,70 +55,114 @@ udr \::Navíc v¾dy pøepoèítáme prùseèíkové události, v¾dy maximálnì dvì odebereme a dvì nové pøidáme. \endalgo -Zbývá rozmyslet si, jaké datové struktury pou¾ijeme, abychom prùseèíky nalezli dostateènì rychle. Pro kalendáø pou¾ijeme napøíklad haldu. Kalendáø -obsahuje v¾dy nejvý¹e $\O(n)$ událostí. Seznam úseèek si budeme udr¾ovat ve vyva¾ovaném stromì, který obsahuje nejvý¹e $\O(n)$ prvkù. Proto jednu -událost kalendáøe doká¾eme vyøe¹it v èase $\O(\log n)$. V¹ech událostí je $\O(n+p)$, a tedy celková slo¾itost algoritmu je $\O((n+p) \log n)$. +Zbývá rozmyslet si, jaké datové struktury pou¾ijeme, abychom prùseèíky nalezli dostateènì rychle. Pro kalendáø pou¾ijeme napøíklad haldu. Prùøez si +budeme udr¾ovat ve vyhledávacím stromì. Poznamenejme, ¾e nemusíme znát souøadnice úseèek, staèí znát jejich poøadí, které se mezi jednotlivými +událostmi nemìní. Pøi pøidávání úseèek procházíme stromem a porovnáváme souøadnice v prùøezu, které prùbì¾nì dopoèítáváme. -Na závìr poznamenejme, ¾e Balaban vymyslel efektivnìj¹í algoritmus, který funguje v èase $\O(n \log n + p)$, ale je podstatnì komplikovanìj¹í. - -\h{Hledání nejbli¾¹ího bodu} - -Nyní se pokusíme vyøe¹it i problém druhé strany. - -{\I Eskymáci tráví vìt¹inu èasu doma, ve svém Iglù. Takový medvìd je na své toulce zasnì¾enou krajinou, kdy¾ tu se najednou rozhodne nav¹tívit nìjakého -Eskymáka. Proto se podívá do své medvìdí mapy a nalezne nejbli¾¹í Iglù. Má to ale jeden háèek, medvìdi toti¾ neumí èíst v mapách!} - -Popí¹eme si nejprve, jak vypadá medvìdí mapa. Medvìdí mapa je {\I Voroného diagram}, co¾ je pro zadané body $x_1, \ldots, x_n$ rozdìlení roviny na -oblasti $B_1, \ldots, B_n$, kde $B_i$ je mno¾ina bodù nejblí¾e k bodu $x_i$. Formálnì jsou tyto oblasti zadefinovány následovnì: -$$B_i = \left\{y \in {\bb R}^2\ \vert\ \forall j:\rho(x_i,y) \le \rho(x_j,y)\right\}.$$ +Kalendáø obsahuje v¾dy nejvý¹e $\O(n)$ událostí. Podobnì prùøez obsahuje v ka¾dém okam¾iku nejvý¹e $\O(n)$ úseèek. Jednu událost kalendáøe doká¾eme +o¹etøit v èase $\O(\log n)$. V¹ech událostí je $\O(n+p)$, a tedy celková slo¾itost algoritmu je $\O((n+p) \log n)$. -Pro dva body $a$ a $b$, mno¾ina v¹ech bodù bli¾¹ích k $a$ ne¾ k $b$ tvoøí polorovinu ohranièenou osou úseèky $ab$. Ka¾dá z oblastí $B_i$ je tvoøena -prùnikem $n-1$ polorovin, tedy je to (mo¾ná neomezený) mnohostìn.\foot{Sly¹eli jste u¾ o lineárním programování? Jak název vùbec nenapoví, -{\I lineární programování} je teorii zabývající se øe¹ením a vlastnostmi soustav lineárních nerovnic. Lineární program je popsaný lineární funkcí, kterou chceme -maximalizovat za podmínek popsaných soustavou lineárních nerovnic. Ka¾dá nerovnice urèuje poloprostor, ve kterém se pøípustná øe¹ení nachází. -Proto¾e pøípustné øe¹ení splòuje v¹echny nerovnice zároveò, je mno¾ina v¹ech pøípustných øe¹ení (mo¾ná neomezený) mnohostìn. Mno¾iny $B_i$ lze -snadno popsat jako mno¾iny v¹ech pøípustných øe¹ení lineárního programù, pomocí vý¹e ukázaných polorovin. Na závìr poznamenejme, ¾e dlouho otevøená -otázka, zda lze nalézt optimální øe¹ení lineárního programu v polynomiálním èase, byla vyøe¹ena, je znám polynomiální algoritmu (kterému se øíká metoda -vnitøního bodu). Na druhou stranu, pokud chceme najít pøípustné celoèíselné øe¹ení, je úloha NP-úplná a je jednoduché na ni pøevést spoustu -optimalizaèních problémù. Dokázat v¹ak, ¾e tento problém le¾í v NP, není vùbec jednoduché.} -Voroneho diagram je naznaèen na obrázku, oblasti $B_i$ jsou ohranièené èernými èárami. +Slíbili jsme, ¾e popí¹eme, jak se vypoøádat s vý¹e uvedenými podmínkami na vstup. Události kalendáøe se stejnou $y$-ovou souøadnicí budeme tøídit v +poøadí zaèátky, prùseèíky a konce úseèek. Tím nahlásíme i prùseèíky krajù úseèek a ani vodorovné úseèky nebudou vadit. Podobnì se není tøeba obávat +prùseèíkù více úseèek v jednom bodì. Úseèky jdoucí stejným smìrem, jejich¾ prùnik je úseèka, jsou komplikovanìj¹í, ale lze jejich prùseèíky o¹etøit a +vypsat tøeba souøadnice úseèky tvoøící jejich prùnik. -\twofigures{8-geom2_2_polorovina.eps}{Body bli¾¹í k $a$ ne¾ $b$.}{1.25in}{8-geom2_3_voroneho_diagram.eps}{Voroneho diagram.}{2.5in} - -Prùnik dvou oblastí mù¾e být, v závislosti na jejich sousedìní, prázdný, bod, úseèka, nebo polopøímka. V na¹em uva¾ování uzavøeme celý Voroneho diagram do -dostateènì velkého obdélníku. Proto¾e okraje mno¾in tvoøí rovinný graf, je podle Eulerovy formule (poèet hran je nejvý¹e $3n-6$) slo¾itost diagramu -$\O(n)$. Voroneho diagram lze zkonstruovat v èase $\O(n \log n)$. Tím se zabývat nebudeme,\foot{Pro zvídavé, kteøí nemají zkou¹ku druhý den ráno: -Detaily naleznete v zápiscích z loòského ADSka.} ale uká¾eme si, jak zadaný Voroneho diagram pou¾ít k rychlému nalezení nejbli¾¹ího bodu. - -Máme zadaný rozklad roviny na konvexní mnohoúhelníky. Chceme pro jednotlivé body rychle rozhodovat, do kterého mnohoúhelníku patøí. Na¹e øe¹ení budeme -optimalizovat pro jeden pevný rozklad a obrovské mno¾ství rùzných dotazù, které chceme co nejrychleji odpovìdìt.\foot{Pøedstavujme si to tøeba tak, ¾e -medvìdùm zprovozníme server. Ten jednou schroustá celou mapu a potom co nejrychleji odpovídá na jejich dotazy. Medvìdi sice neumí èíst v mapách, ale -pøipojit se na server hravì zvládnou!} Nejprve pøedzpracujeme Voroneho diagram a vytvoøíme strukturu, která nám umo¾ní rychlé dotazy na jednotlivé -body. - -Uka¾me si nejprve øe¹ení bez pøedzpracování. Rovinu budeme zametat pøímkou shora dolù. Podobnì jako pøi hledání prùseèíkù úseèek, udr¾ujeme si prùøez -pøímky. V¹imnìte si, ¾e tento prùøez se mìní jenom ve vrcholech mnohoúhelníkù. Ve chvíli, kdy narazíme na hledaný bod, podíváme se, do kterého -intervalu v prùøezu patøí, a ten nahlásíme. Prùøez budeme uchovávat ve vyhledávacím stromì. Takové øe¹ení má slo¾itost $\O(n \log n)$ na dotaz, co¾ je -hroznì pomalé. +Na závìr poznamenejme, ¾e Balaban vymyslel efektivnìj¹í algoritmus, který funguje v èase $\O(n \log n + p)$, ale je podstatnì komplikovanìj¹í. -Pøedzpracování bude fungovat následovnì. Rozøe¾eme si celou rovinu na pásy, bìhem kterých se prùøez pøímkou nemìní. Pro ka¾dý z nich si budeme -pamatovat stav stromu, ve kterém se nacházel prùøez pøi procházení tímto pásem. Kdy¾ chceme lokalizovat nìjaký bod, nejprve pùlením nalezneme pás, v -kterém le¾í. Poté polo¾íme dotaz na pøíslu¹ný strom. Dotaz doká¾eme zodpovìdìt v èase $\O(\log n)$. +\h{Hledání nejbli¾¹ích bodù a Voroného diagramy} + +Nyní se pokusíme vyøe¹it i problém druhé strany -- pomù¾eme medvìdùm nalézt Eskymáky. + +{\I Eskymáci tráví vìt¹inu èasu doma, ve svém iglù. Takový medvìd je na své toulce zasnì¾enou krajinou, kdy¾ tu se najednou rozhodne nav¹tívit nìjakého +Eskymáka. Proto se podívá do své medvìdí mapy a nalezne nejbli¾¹í iglù. Má to ale jeden háèek, iglù jsou spousty a medvìd by dávno usnul, ne¾ by +nejbli¾¹í objevil.}\foot{Zlí jazykové by øekli, ¾e medvìdi jsou moc líní a nebo v mapách ani èíst neumí!} + +Popí¹eme si nejprve, jak vypadá medvìdí mapa. Medvìdí mapa obsahuje celou Arktidu a jsou v ní vyznaèena v¹echna iglù. Navíc obsahuje vyznaèené +oblasti tvoøené body, které jsou nejblí¾e k jednomu danému iglù. Takovému schématu se øíká {\I Voroného diagram}. Ten pro zadané body $x_1, \ldots, x_n$ +obsahuje rozdìlení roviny na oblasti $B_1, \ldots, B_n$, kde $B_i$ je mno¾ina bodù, které jsou blí¾e k $x_i$ ne¾ k ostatním bodùm $x_j$. Formálnì jsou +tyto oblasti definovány následovnì: +$$B_i = \left\{y \in {\bb R}^2\ \vert\ \forall j:\rho(x_i,y) \le \rho(x_j,y)\right\},$$ +kde $\rho(x,y)$ znaèí vzdálenost bodù $x$ a $y$. + +Uká¾eme si, ¾e Voroného diagram má pøekvapivì jednoduchou strukturu. Nejprve uva¾me, jak budou vypadat oblasti $B_a$ a $B_b$ pouze pro dva body +$a$ a $b$, jak je naznaèeno na obrázku. V¹echny body stejnì vzdálené od $a$ i $b$ le¾í na pøímce $p$ -- ose úseèky $ab$. Oblasti $B_a$ a $B_b$ +jsou tedy tvoøeny polorovinami ohranièenými osou $p$. Tedy obecnì tvoøí mno¾ina v¹ech bodù bli¾¹ích k $x_i$ ne¾ k $x_j$ nìjakou polorovinu. Oblast +$B_i$ obsahuje v¹echny body, které jsou souèasnì bli¾¹í k $x_i$ ne¾ ke v¹em ostatním bodùm $x_j$ -- tedy le¾í ve v¹ech polorovinách souèasnì. +Ka¾dá z oblastí $B_i$ je tvoøena prùnikem $n-1$ polorovin, tedy je to (mo¾ná neomezený) mnohoúhelník.\foot{Sly¹eli jste u¾ o lineárním programování? +Jak název vùbec nenapoví, {\I lineární programování} je teorii zabývající se øe¹ením a vlastnostmi soustav lineárních nerovnic. Lineární program je +popsaný lineární funkcí, kterou chceme maximalizovat za podmínek popsaných soustavou lineárních nerovnic. Ka¾dá nerovnice urèuje poloprostor, ve +kterém se pøípustná øe¹ení nachází. Proto¾e pøípustné øe¹ení splòuje v¹echny nerovnice zároveò, je mno¾ina v¹ech pøípustných øe¹ení (mo¾ná neomezený) +mnohostìn, obecnì ve veliké dimenzi ${\bb R}^d$, kde $d$ je poèet promìnných. Mno¾iny $B_i$ lze snadno popsat jako mno¾iny v¹ech pøípustných øe¹ení +lineárních programù pomocí vý¹e ukázaných polorovin. Na závìr poznamenejme, ¾e dlouho otevøená otázka, zda lze nalézt optimální øe¹ení lineárního +programu v polynomiálním èase, byla pozitivnì vyøe¹ena -- je znám polynomiální algoritmus, kterému se øíká {\I metoda vnitøního bodu}. Na druhou +stranu, pokud chceme najít pøípustné celoèíselné øe¹ení, je úloha NP-úplná a je jednoduché na ni pøevést spoustu optimalizaèních problémù. Dokázat +NP-tì¾kost není pøíli¹ tì¾ké. Na druhou stranu ukázat, ¾e tento problém le¾í v NP, není vùbec jednoduché.} +Pøíklad Voroného diagram je naznaèen na obrázku. Zadané body jsou oznaèeny prázdnými krou¾ky a hranice oblastí $B_i$ jsou vyznaèené èernými èárami. + +\twofigures{8-geom2_2_polorovina.eps}{Body bli¾¹í k $a$ ne¾ $b$.}{1.25in} + {8-geom2_3_voroneho_diagram.eps}{Voroného diagram.}{2.5in} + +Není náhoda, pokud vám hranice oblastí pøipomíná rovinný graf. Jeho vrcholy jsou body, které jsou stejnì vzdálené od alespoò tøí zadaných bodù. Jeho +stìny jsou oblasti $B_i$. Jeho hrany jsou tvoøeny èástí hranice mezi dvìma oblastmi -- body, které mají dvì oblasti spoleèné. Obecnì prùnik dvou +oblastí mù¾e být, v závislosti na jejich sousedìní, prázdný, bod, úseèka, polopøímka nebo dokonce celá pøímka. V dal¹ím textu si pøedstavme, ¾e celý +Voroného diagram uzavøeme do dostateènì velkého obdélníka,\foot{Pøeci jenom i celá Arktida je omezenì velká.} èím¾ dostaneme omezený rovinný graf. + +Poznamenejme, ¾e pøeru¹ované èáry tvoøí hrany duálního rovinného grafu s vrcholy v zadaných bodech. Hrany spojují sousední body na kru¾nicích, které +obsahují alespoò tøi ze zadaných bodù. Napøíklad na obrázku dostáváme skoro samé trojúhelníky, proto¾e vìt¹ina kru¾nic obsahuje pøesnì tøi zadané +body. Av¹ak nalezneme i jeden ètyøúhelník, jeho¾ vrcholy le¾í na jedné kru¾nici. + +Zkusíme nyní odhadnout, jak velký je rovinný graf popisující Voroného diagram. Podle slavné Eulerovy formule má ka¾dý rovinný graf nejvý¹e lineárnì +mnoho vrcholù, hran a stìn -- pro $v$ vrcholù, $e$ hran a $f$ stìn je $e \le 3v-6$ a navíc $v+f = e+2$. Tedy slo¾itost diagramu je lineární vzhledem k +poètu zadaných bodù $n=f$, $\O(n)$. Navíc Voroného diagram lze zkonstruovat v èase $\O(n \log n)$, napøíklad pomocí zametání roviny nebo metodou +rozdìl a panuj. Tím se v¹ak zabývat nebudeme,\foot{Pro zvídavé, kteøí nemají zkou¹ku druhý den ráno: Detaily naleznete v zápiscích z pøedloòského +ADSka.} místo toho si uká¾eme, jak v ji¾ spoèteném Voroného diagramu rychlé hledat nejbli¾¹í body. + +\h{Lokalizace bodu uvnitø mnohoúhelníkové sítì} + +Problém medvìdù je najít v medvìdí mapì co nejrychleji nejbli¾¹í iglù. Máme v rovinì sí» tvoøenou mnohoúhelníky. Chceme pro jednotlivé body rychle +rozhodovat, do kterého mnohoúhelníku patøí. Na¹e øe¹ení budeme optimalizovat pro jeden pevný rozklad a obrovské mno¾ství rùzných dotazù, které chceme +co nejrychleji zodpovìdìt.\foot{Pøedstavujme si to tøeba tak, ¾e medvìdùm zprovozníme server. Ten jednou schroustá celou mapu a potom co nejrychleji +odpovídá na jejich dotazy. Medvìdi tak nemusí v mapách nic hledat, staèí se pøipojit na server a poèkat na odpovìï.} Nejprve pøedzpracujeme zadané +mnohoúhelníky a vytvoøíme strukturu, která nám umo¾ní rychlé dotazy na jednotlivé body. + +Uka¾me si pro zaèátek øe¹ení bez pøedzpracování. Rovinu budeme zametat pøímkou shora dolù. Podobnì jako pøi hledání prùseèíkù úseèek, udr¾ujeme si prùøez +pøímkou. V¹imnìte si, ¾e tento prùøez se mìní jenom ve vrcholech mnohoúhelníkù. Ve chvíli, kdy narazíme na hledaný bod, podíváme se, do kterého +intervalu v prùøezu patøí. To nám dá mnohoúhelník, který nahlásíme. Prùøez budeme uchovávat ve vyhledávacím stromì. Takové øe¹ení má slo¾itost $\O(n +\log n)$ na dotaz, co¾ je hroznì pomalé. + +Pøedzpracování bude fungovat následovnì. Jak je naznaèeno na obrázku pøeru¹ovanými èárami, rozøe¾eme si celou rovinu na pásy, bìhem kterých se prùøez +pøímkou nemìní. Pro ka¾dý z nich pamatujeme stav stromu popisující, jak vypadal prùøez pøi procházení tímto pásem. Kdy¾ chceme lokalizovat nìjaký bod, +nejprve pùlením nalezneme pás, v kterém se nachází. Poté polo¾íme dotaz na pøíslu¹ný strom. Strom procházíme a po cestì si dopoèítáme souøadnice +prùøezu, a¾ lokalizujeme správný interval v prùøezu. Dotaz doká¾eme zodpovìdìt v èase $\O(\log n)$. Hledaný bod je na obrázku naznaèen prázdným +koleèkem a nalezený interval v prùøezu je vyta¾ený tuènì. + +\figure{8-geom2_4_pasy_mnohouhelniku.eps}{Mnohoúhelníky rozøezané na pásy.}{2.5in} Jenom¾e na¹e øe¹ení má jeden háèek: Jak zkonstruovat jednotlivé verze stromu dostateènì rychle? K tomu napomohou {\I èásteènì perzistentní} datové -struktury. Pod perzistencí se myslí, ¾e struktura si umo¾òuje uchovávat svoji historii. Èásteènì perzistentní struktury nemohou svoji historii +struktury. Pod perzistencí se myslí, ¾e struktura umo¾òuje uchovávat svoji historii. Èásteènì perzistentní struktury nemohou svoji historii modifikovat. Popí¹eme si, jak vytvoøit perzistentní strom s pamìtí $\O(\log n)$ na zmìnu. Pokud provádíme operaci na stromì, mìní se jenom malá èást stromu. -Napøíklad pøi vkládání do stromu se mìní jenom prvky na jedné cestièce z koøene do listu (a pøípadnì rotací jejím nejbli¾¹ím okolí). Proto si ulo¾íme -upravenou cestièku a zbytek stromu budeme sdílet s pøedchozí verzí. Mimochodem zmìny ka¾dé operace se slo¾itostí $\O(k)$ lze zapsat v pamìti -$\O(k)$, prostì operace nemá tolik èasu, aby mohla pozmìnit pøíli¹ velikou èást stromu. +Napøíklad pøi vkládání do stromu se mìní jenom prvky na jedné cestièce z koøene do listu (a pøípadnì rotací i na jejím nejbli¾¹ím okolí). Proto si +ulo¾íme upravenou cestièku a zbytek stromu budeme sdílet s pøedchozí verzí. Na obrázku je vyznaèena cesta, její¾ vrcholy jsou upravovány. ©edì +oznaèené podstromy navì¹ené na tuto cestu se nemìní, a proto na nì staèí zkopírovat ukazatele. Mimochodem zmìny ka¾dé operace se slo¾itostí $\O(k)$ +lze zapsat v pamìti $\O(k)$, prostì operace nemá tolik èasu, aby mohla pozmìnit pøíli¹ velikou èást stromu. + +\figure{8-geom2_5_upravy_stromu.eps}{Jedna operace mìní pouze okolí cesty -- navì¹ené podstromy se nemìní.}{2in} -Celková èasová slo¾itost je tedy $\O(n \log n)$ na pøedzpracování Voroneho diagramu a vytvoøení persistentního stromu. Kvùli persistenci potøebuje +Celková èasová slo¾itost je tedy $\O(n \log n)$ na pøedzpracování Voroného diagramu a vytvoøení persistentního stromu. Kvùli persistenci potøebuje toto pøedzpracování pamì» $\O(n \log n)$. Na dotaz spotøebujeme èas $\O(\log n)$, nebo» nejprve vyhledáme pùlením pøíslu¹ný pás a poté polo¾íme dotaz -na pøíslu¹nou verzi stromu. Rychleji ani celou operaci provést nepùjde, proto¾e potøebujeme utøídit souøadnice bodù. Na závìr poznamenejme, ¾e se umí -provést vý¹e uvedená persistence vyhledávacího stromu v amortizované pamìti $\O(1)$ na zmìnu. My¹lenka je, ¾e pou¾ijeme stromy, které pøi insertu a -deletu provádí amortizovanì jenom konstantnì mnoho úprav své struktury. To nám napøíklad zaruèí 2-4 stromy z pøedná¹ky a podobnou vlastnost lze -dokázat i o èervenoèerných stromech. Pøi zmìnì potom nebudeme upravovat celou cestu, ale upravíme jenom jednotlivé vrcholy, kterých se zmìna týká. +na pøíslu¹nou verzi stromu. Rychleji to ani provést nepùjde, nebo» potøebujeme utøídit souøadnice bodù. + +\s{Lze to lépe?} Na závìr poznamenejme, ¾e se umí provést vý¹e popsaná persistence vyhledávacího stromu v amortizované pamìti $\O(1)$ na zmìnu. Ve +struènosti naznaèíme my¹lenku. Pou¾ijeme stromy, které pøi insertu a deletu provádí amortizovanì jenom konstantnì mnoho úprav své struktury. To nám +napøíklad zaruèí 2-4 stromy z pøedná¹ky a podobnou vlastnost lze dokázat i o èerveno-èerných stromech. Pøi zmìnì potom nebudeme upravovat celou cestu, +ale upravíme jenom jednotlivé vrcholy, kterých se zmìna týká. Ka¾dý vrchol stromu si v sobì bude pamatovat a¾ dvì své verze. Pokud chceme vytvoøit +tøetí verzi, vrchol zkopírujeme stranou. To v¹ak mù¾e vyvolat zmìny v jeho rodièích a¾ do koøene. Situace je naznaèena na obrázku. Pøi vytvoøení nové +verze $3$ pro vrcholu $v$ vytvoøíme jeho kopii $v'$, do které ulo¾íme tuto verzi. Av¹ak musíme také zmìnit rodièe $u$, kterému vytvoøíme novou verzi +ukazující na $v'$. Abychom dosáhli ký¾ené konstantní pamì»ové slo¾itosti, pomù¾e potenciálový argument -- zmìn se provádí amortizovanì jenom +konstantnì mnoho. Navíc si pro ka¾dou verzi pamatujeme její koøen, ze kterého máme dotaz spustit. + +\figure{8-geom2_6_rychla_perzistence.eps}{Vytvoøení nové verze vrcholu.}{2in} \bye diff --git a/8-geom2/8-geom2_1_usecky.eps b/8-geom2/8-geom2_1_usecky.eps index 4edc7e6..7d33366 100644 --- a/8-geom2/8-geom2_1_usecky.eps +++ b/8-geom2/8-geom2_1_usecky.eps @@ -2,7 +2,7 @@ %%BoundingBox: -2 -39 116 45 %%HiResBoundingBox: -1.99252 -38.843 115.37833 44.5122 %%Creator: MetaPost 0.993 -%%CreationDate: 2009.12.16:0304 +%%CreationDate: 2010.01.10:1711 %%Pages: 1 %%BeginProlog %%EndProlog diff --git a/8-geom2/8-geom2_2_polorovina.eps b/8-geom2/8-geom2_2_polorovina.eps index eae45e7..f55aeac 100644 --- a/8-geom2/8-geom2_2_polorovina.eps +++ b/8-geom2/8-geom2_2_polorovina.eps @@ -2,9 +2,10 @@ %%BoundingBox: -39 -86 55 90 %%HiResBoundingBox: -38.45198 -85.83585 54.56447 89.41768 %%Creator: MetaPost 0.993 -%%CreationDate: 2009.12.16:0304 +%%CreationDate: 2010.01.10:1711 %%Pages: 1 -%*Font: cmmi10 9.96265 9.96265 61:c +%*Font: cmmi10 9.96265 9.96265 42:800000018002 +%*Font: cmmi7 6.97385 6.97385 61:c %%BeginProlog %%EndProlog %%Page: 1 1 @@ -18,6 +19,22 @@ newpath 0.09926 88.67047 moveto [] 0 setdash 1 setlinecap 1 setlinejoin 10 setmiterlimit newpath 0.09926 88.67047 moveto 48.08961 -74.49722 lineto stroke +newpath 40.57065 -58.97935 moveto +16.09567 -66.17786 lineto stroke +newpath 19.20924 -63.66643 moveto +16.09567 -66.17786 lineto +20.07314 -66.60371 lineto + closepath +gsave fill grestore stroke +newpath 2.17896 71.55281 moveto +-22.29602 64.35431 lineto stroke +newpath -19.18245 66.86574 moveto +-22.29602 64.35431 lineto +-18.31856 63.92845 lineto + closepath +gsave fill grestore stroke +10.29752 63.02016 moveto +(p) cmmi10 9.96265 fshow 0 0.5 dtransform truncate idtransform setlinewidth pop [3 3 ] 0 setdash newpath 0 0 moveto @@ -66,5 +83,13 @@ newpath 50.1814 14.17323 moveto (a) cmmi10 9.96265 fshow 50.28886 16.27322 moveto (b) cmmi10 9.96265 fshow +-11.8578 25.68977 moveto +(B) cmmi10 9.96265 fshow +-4.3011 24.19537 moveto +(a) cmmi7 6.97385 fshow +36.74002 39.863 moveto +(B) cmmi10 9.96265 fshow +44.29672 38.3686 moveto +(b) cmmi7 6.97385 fshow showpage %%EOF diff --git a/8-geom2/8-geom2_3_voroneho_diagram.eps b/8-geom2/8-geom2_3_voroneho_diagram.eps index d32083e..9c462f5 100644 --- a/8-geom2/8-geom2_3_voroneho_diagram.eps +++ b/8-geom2/8-geom2_3_voroneho_diagram.eps @@ -1,8 +1,8 @@ %!PS -%%BoundingBox: -82 -96 91 107 -%%HiResBoundingBox: -81.19815 -95.708 90.92032 106.73361 +%%BoundingBox: -82 -96 92 107 +%%HiResBoundingBox: -81.19815 -95.708 91.0566 106.89594 %%Creator: MetaPost 0.993 -%%CreationDate: 2009.12.16:0304 +%%CreationDate: 2010.01.10:1711 %%Pages: 1 %%BeginProlog %%EndProlog @@ -18,15 +18,15 @@ newpath -39.01674 0.74886 moveto -12.65121 41.49461 lineto -50.21571 104.10237 lineto stroke newpath -12.65121 41.49461 moveto -43.8882 62.05504 lineto -84.44029 105.9864 lineto stroke -newpath 43.8882 62.05504 moveto -36.59952 -3.53217 lineto +44.01595 62.10149 lineto +84.41986 106.14873 lineto stroke +newpath 44.01595 62.10149 moveto +36.77472 -3.66359 lineto -13.44022 33.99786 lineto stroke -newpath 36.59952 -3.53217 moveto -36.70383 -3.7555 lineto -90.17311 -10.04572 lineto stroke -newpath 36.70383 -3.7555 moveto +newpath 36.77472 -3.66359 moveto +36.77475 -3.6633 lineto +90.30939 -10.22003 lineto stroke +newpath 36.77475 -3.6633 moveto 5.74025 -44.00813 lineto stroke 0 0.5 dtransform truncate idtransform setlinewidth pop [3 3 ] 0 setdash @@ -39,22 +39,22 @@ newpath 0 0 moveto newpath -49.74837 38.26788 moveto 7.65346 72.70874 lineto 22.96097 30.61443 lineto -0 0 lineto -57.40182 26.7874 lineto +0 0 lineto stroke +newpath 57.71597 26.7874 moveto 49.74837 -38.26788 lineto stroke -newpath 57.40182 26.7874 moveto +newpath 57.71597 26.7874 moveto 7.65346 72.70874 lineto stroke newpath -49.74837 38.26788 moveto 22.96097 30.61443 lineto -57.40182 26.7874 lineto stroke +57.71597 26.7874 lineto stroke 0 3.98505 dtransform truncate idtransform setlinewidth pop [] 0 setdash newpath 5.74025 -44.00813 moveto 0 0 rlineto stroke newpath -39.01674 0.74886 moveto 0 0 rlineto stroke newpath -13.44022 33.99786 moveto 0 0 rlineto stroke newpath -12.65121 41.49461 moveto 0 0 rlineto stroke -newpath 43.8882 62.05504 moveto 0 0 rlineto stroke -newpath 36.59952 -3.53217 moveto 0 0 rlineto stroke -newpath 36.70383 -3.7555 moveto 0 0 rlineto stroke +newpath 44.01595 62.10149 moveto 0 0 rlineto stroke +newpath 36.77472 -3.66359 moveto 0 0 rlineto stroke +newpath 36.77475 -3.6633 moveto 0 0 rlineto stroke 1 1 1 setrgbcolor newpath 1.99252 0 moveto 1.99252 0.52847 1.78256 1.03523 1.4089 1.4089 curveto @@ -119,25 +119,25 @@ newpath 51.74089 -38.26788 moveto 51.53093 -39.30312 51.74089 -38.79636 51.74089 -38.26788 curveto closepath stroke 1 1 1 setrgbcolor -newpath 59.39435 26.7874 moveto -59.39435 27.31587 59.18439 27.82263 58.81073 28.1963 curveto -58.43706 28.56996 57.9303 28.77992 57.40182 28.77992 curveto -56.87335 28.77992 56.3666 28.56996 55.99292 28.1963 curveto -55.61926 27.82263 55.4093 27.31587 55.4093 26.7874 curveto -55.4093 26.25893 55.61926 25.75217 55.99292 25.3785 curveto -56.3666 25.00484 56.87335 24.79488 57.40182 24.79488 curveto -57.9303 24.79488 58.43706 25.00484 58.81073 25.3785 curveto -59.18439 25.75217 59.39435 26.25893 59.39435 26.7874 curveto closepath fill +newpath 59.7085 26.7874 moveto +59.7085 27.31587 59.49854 27.82263 59.12488 28.1963 curveto +58.7512 28.56996 58.24445 28.77992 57.71597 28.77992 curveto +57.1875 28.77992 56.68074 28.56996 56.30707 28.1963 curveto +55.93341 27.82263 55.72345 27.31587 55.72345 26.7874 curveto +55.72345 26.25893 55.93341 25.75217 56.30707 25.3785 curveto +56.68074 25.00484 57.1875 24.79488 57.71597 24.79488 curveto +58.24445 24.79488 58.7512 25.00484 59.12488 25.3785 curveto +59.49854 25.75217 59.7085 26.25893 59.7085 26.7874 curveto closepath fill 0 0 0 setrgbcolor -newpath 59.39435 26.7874 moveto -59.39435 27.31587 59.18439 27.82263 58.81073 28.1963 curveto -58.43706 28.56996 57.9303 28.77992 57.40182 28.77992 curveto -56.87335 28.77992 56.3666 28.56996 55.99292 28.1963 curveto -55.61926 27.82263 55.4093 27.31587 55.4093 26.7874 curveto -55.4093 26.25893 55.61926 25.75217 55.99292 25.3785 curveto -56.3666 25.00484 56.87335 24.79488 57.40182 24.79488 curveto -57.9303 24.79488 58.43706 25.00484 58.81073 25.3785 curveto -59.18439 25.75217 59.39435 26.25893 59.39435 26.7874 curveto closepath stroke +newpath 59.7085 26.7874 moveto +59.7085 27.31587 59.49854 27.82263 59.12488 28.1963 curveto +58.7512 28.56996 58.24445 28.77992 57.71597 28.77992 curveto +57.1875 28.77992 56.68074 28.56996 56.30707 28.1963 curveto +55.93341 27.82263 55.72345 27.31587 55.72345 26.7874 curveto +55.72345 26.25893 55.93341 25.75217 56.30707 25.3785 curveto +56.68074 25.00484 57.1875 24.79488 57.71597 24.79488 curveto +58.24445 24.79488 58.7512 25.00484 59.12488 25.3785 curveto +59.49854 25.75217 59.7085 26.25893 59.7085 26.7874 curveto closepath stroke 1 1 1 setrgbcolor newpath 24.95349 30.61443 moveto 24.95349 31.1429 24.74353 31.64966 24.36987 32.02333 curveto diff --git a/8-geom2/lib.mp b/8-geom2/lib.mp index 2536305..cbeedf5 100644 --- a/8-geom2/lib.mp +++ b/8-geom2/lib.mp @@ -45,6 +45,8 @@ def drawfvertices(expr s,n,flags) = endfor enddef; +path centersquare; centersquare := (-0.5,-0.5)--(0.5,-0.5)--(0.5,0.5)--(-0.5,0.5)--cycle; + def vertex(expr p) = p withpen pencircle scaled 4pt enddef; def drawemptyvertex(expr p) = unfill fullcircle scaled 4pt shifted p; draw fullcircle scaled 4pt shifted p; enddef; def drawendpointvertex(expr p) = draw vertex(p) withcolor red; draw fullcircle scaled 6pt shifted p; enddef; -- 2.39.2