\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}
\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
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ì:
\::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
projects / ads2.git / blobdiff