From fd3df33dfc94645a52025c193b4a0dcd85d9c7c6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 9 Jan 2012 18:15:27 +0100 Subject: [PATCH] Geometrie: Castecne upravy castecne persistence --- 6-geom/6-geom.tex | 47 +++++++++++++++++++++++++++++------------------ 1 file changed, 29 insertions(+), 18 deletions(-) diff --git a/6-geom/6-geom.tex b/6-geom/6-geom.tex index 6a89a88..b97ad6d 100644 --- a/6-geom/6-geom.tex +++ b/6-geom/6-geom.tex @@ -287,7 +287,7 @@ obecn úpravy. Na závìr poznamenejme, ¾e existuje efektivnìj¹í, by» daleko komplikovanìj¹í, -algoritmus od Balabana dosahující èasové slo¾itosti $\O(n \log n + p)$. +algoritmus od Chazella dosahující èasové slo¾itosti $\O(n \log n + p)$. \h{Hledání nejbli¾¹ích bodù a Voroného diagramy} @@ -325,12 +325,12 @@ body. Av 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 rychle hledat nejbli¾¹í body. +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~ADS z~roku 2007/2008.} +místo toho si uká¾eme, jak v ji¾ spoèteném Voroného diagramu rychle 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 +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é @@ -342,22 +342,33 @@ intervalu v pr \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 si 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, ve 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 +pøímkou nemìní. Pro ka¾dý z nich si pamatujeme stav stromu tak, 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, ve kterém se nachází $y$-ová souøadnice bodu. 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 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í 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_4_pasy_mnohouhelniku.eps}{Mnohoúhelníky rozøezané na pásy}{2.5in} + +Kdybychom si ov¹em uchovávali stavy stromu tak, ¾e bychom si pro ka¾dý pás poøídili kopii celého +stromu, spotøebovali bychom jenom kopírováním stromù èas i pamì» $\Theta(n^2\log n)$. Místo toho +si poøídíme {\I èásteènì persistentní} vyhledávací strom -- ten který si pamatuje historii v¹ech +svých zmìn a umí v~ní vyhledávat. Pøesnìji øeèeno, po~ka¾dé operaci, která mìní stav stromu, +vznikne nová {\I verze} stromu a operace pro hledání dostanou jako dal¹í parametr identifikátor +verze, ve~které mají hledat.\foot{Plnì persistentní struktura by na rozdíl od èásteènì persistentní +umìla star¹í verze i upravovat, èím¾ by se historie rozvìtvila. To pro na¹e úèely není potøeba.} + +Popí¹eme jednu z~mo¾ných konstrukcí persistentního stromu. Uva¾ujme obyèejný vyhledávací strom, +øeknìme AVL strom. Rozhodneme se ale, ¾e jeho vrcholy nikdy nebudeme mìnit, abychom neporu¹ili +zaznamenanou historii. Místo toho si poøídíme kopii vrcholu a tu zmìníme. Musíme ov¹em zmìnit +ukazatel na daný vrchol, aby ukazoval na kopii. Proto zkopírujeme i jeho otce a upravíme v~nìm +ukazatel. Tím pádem musíme upravit i ukazatel na otce, atd., a¾ se dostaneme do koøene. Kopie +koøene se pak stane identifikátorem nové verze. + +Zkopírovali jsme tedy celou cestu mezi koøenem stromu a upravovaným vrcholem. Uchování +jedné verze nás tedy strojí èas $\O(\log n)$ a prostor takté¾ $\O(\log n)$. Je¹tì nesmíme +zapomenout, ¾e po ka¾dé operaci následuje vyvá¾ení stromu. To ov¹em upravuje pouze vrcholy, +které le¾í v~konstantní vzdálenosti od~cesty z~místa úpravy do koøene, tak¾e jejich zkopírováním +èasovou ani prostorou slo¾itost nezhor¹íme. \figure{8-geom2_5_upravy_stromu.eps}{Jedna operace mìní pouze okolí cesty -- navì¹ené podstromy se nemìní.}{2in} -- 2.39.5