From 99b7436f238e8ee1ad693c04cff0925ccc9ef46b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 15 Jan 2012 15:57:16 +0100 Subject: [PATCH] Geometrie: Vycistena cast o lokalizaci bodu --- 6-geom/6-geom.tex | 62 +++++++++----- 6-geom/8-geom2_6_rychla_perzistence.eps | 106 ------------------------ 2 files changed, 42 insertions(+), 126 deletions(-) delete mode 100644 6-geom/8-geom2_6_rychla_perzistence.eps diff --git a/6-geom/6-geom.tex b/6-geom/6-geom.tex index b97ad6d..909d4f4 100644 --- a/6-geom/6-geom.tex +++ b/6-geom/6-geom.tex @@ -308,7 +308,7 @@ kde $\rho(x,y)$ zna 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 +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. Pøíklad Voroného diagramu 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. @@ -316,15 +316,23 @@ P 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. +Voroného diagram uzavøeme do dostateènì velkého obdélníka, èí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 +Zkusíme nyní odhadnout, jak velký je rovinný graf popisující Voroného diagram. +Pro rovinné grafy bez násobných hran obecnì platí, ¾e mají nejvý¹e lineárnì +mnoho hran vzhledem k~vrcholùm. My ov¹em neznáme poèet vrcholù, nýbr¾ poèet stìn +-- ka¾dá stìna odpovídá jednomu ze zadaných bodù. Proto odhad poètu hran pou¾ijeme +na duál na¹eho grafu, èím¾ prohodíme vrcholy se stìnami a hran zùstane stejnì. +®ádnou násobnou hranu jsme tím nepøidali, ta by toti¾ odpovídala stìnì velikosti~2 +ve~Voroného diagramu a takové neexistují, nebo» ka¾dá stìna je ohranièena rovnými +èarami. + +Voroneho diagram pro $n$~zadaných bodù je tedy velký $\O(n)$. Dodejme, ¾e ho lze +zkonstruovat 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~ADS z~roku 2007/2008.} místo toho si uká¾eme, jak v ji¾ spoèteném Voroného diagramu rychle hledat nejbli¾¹í body. @@ -351,11 +359,10 @@ kole 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 +si poøídíme {\I persistentní} vyhledávací strom -- ten 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.} +verze, ve~které mají hledat. 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 @@ -374,17 +381,32 @@ kter 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 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} +na pøíslu¹nou verzi stromu. + +\s{Lze to lépe?} Na závìr poznamenejme, ¾e spotøeba pamìti $\Theta(\log n)$ +na ulo¾ení jedné verze je zbyteènì vysoká. Existuje o~nìco chytøej¹í konstrukce +persistentního stromu, které staèí konstantní pamì», alespoò amortizovanì. +Nastíníme, jak funguje. + +Nejprve si poøídíme vyhledávací strom, který pøi ka¾dém vlo¾ení nebo smazání +prvku provede jen amortizovanì konstantní poèet {\I strukturálních zmìn} +(to jsou zmìny hodnot a ukazatelù, zkrátka v¹eho, podle èeho se øídí +vyhledávání a co je tedy potøeba verzovat; zmìna poèítadla ve~vrcholu +u~AVL-stromu tedy strukturální není). Tuto vlastnost mají tøeba 2,4-stromy +nebo nìkteré varianty èerveno-èerných stromù. + +Nyní uká¾eme, jak jednu strukturální zmìnu zaznamenat v~amortizovanì +konstantním prostoru. Ka¾dý vrchol stromu si tentokrát bude pamatovat +dvì své verze (spolu s~èasy jejich vzniku). Pøi prùchodu od~koøene +porovnáme èas vzniku tìchto verzí s~aktuálním èasem a vybereme si +správnou verzi. Pokud potøebujeme zaznamenat novou verzi vrcholu, buïto +na ni ve~vrcholu je¹tì je místo, nebo není a v~takovém pøípadì vrchol +zkopírujeme, co¾ vynutí zmìnu ukazatele v~rodièi, a~tedy i vytvoøení +nové verze rodièe, atd. a¾ pøípadnì do koøene. Identifikátorem verze +celé datové struktury bude ukazatel na aktuální kopii koøene. + +Jedna operace mù¾e v~nejhor¹ím pøípadì zpùsobit zkopírování v¹ech +vrcholù a¾ do koøene, ale jednoduchým potenciálovým argumentem lze +dokázat, ¾e poèet kopií bude amortizovanì konstantní. \bye diff --git a/6-geom/8-geom2_6_rychla_perzistence.eps b/6-geom/8-geom2_6_rychla_perzistence.eps deleted file mode 100644 index 8085675..0000000 --- a/6-geom/8-geom2_6_rychla_perzistence.eps +++ /dev/null @@ -1,106 +0,0 @@ -%!PS -%%BoundingBox: -78 -58 78 76 -%%HiResBoundingBox: -77.69408 -57.73378 77.69408 75.84055 -%%Creator: MetaPost 0.993 -%%CreationDate: 2010.01.10:1711 -%%Pages: 1 -%*Font: cmmi10 9.96265 9.96265 75:c -%*Font: cmr10 9.96265 9.96265 31:e000000000000800444 -%*Font: cmsy7 6.97385 6.97385 30:8 -%%BeginProlog -%%EndProlog -%%Page: 1 1 - 0 0 0 setrgbcolor 0 0.5 dtransform truncate idtransform setlinewidth pop - [] 0 setdash 1 setlinejoin 10 setmiterlimit -newpath -77.44408 -28.34645 moveto --20.75117 -28.34645 lineto --20.75117 -9.4488 lineto --77.44408 -9.4488 lineto - closepath stroke -newpath -77.44408 -47.2441 moveto --20.75117 -47.2441 lineto --20.75117 -28.34645 lineto --77.44408 -28.34645 lineto - closepath stroke --64.33218 -22.10783 moveto -(v) cmr10 9.96265 fshow --59.35089 -22.10783 moveto -(erze) cmr10 9.96265 fshow --38.84439 -22.10783 moveto -(2) cmr10 9.96265 fshow --64.33218 -41.00548 moveto -(v) cmr10 9.96265 fshow --59.35089 -41.00548 moveto -(erze) cmr10 9.96265 fshow --38.84439 -41.00548 moveto -(1) cmr10 9.96265 fshow --51.69093 -54.53358 moveto -(v) cmmi10 9.96265 fshow -newpath 20.75117 -28.34645 moveto -77.44408 -28.34645 lineto -77.44408 -9.4488 lineto -20.75117 -9.4488 lineto - closepath stroke -newpath 20.75117 -47.2441 moveto -77.44408 -47.2441 lineto -77.44408 -28.34645 lineto -20.75117 -28.34645 lineto - closepath stroke -33.86307 -22.10783 moveto -(v) cmr10 9.96265 fshow -38.84436 -22.10783 moveto -(erze) cmr10 9.96265 fshow -59.35086 -22.10783 moveto -(3) cmr10 9.96265 fshow -45.10683 -57.73378 moveto -(v) cmmi10 9.96265 fshow -50.29343 -54.11838 moveto -(0) cmsy7 6.97385 fshow -newpath -28.34645 56.6929 moveto -28.34645 56.6929 lineto -28.34645 75.59055 lineto --28.34645 75.59055 lineto - closepath stroke -newpath -28.34645 37.79526 moveto -28.34645 37.79526 lineto -28.34645 56.6929 lineto --28.34645 56.6929 lineto - closepath stroke --15.23456 62.93152 moveto -(v) cmr10 9.96265 fshow --10.25327 62.93152 moveto -(erze) cmr10 9.96265 fshow -10.25323 62.93152 moveto -(2) cmr10 9.96265 fshow --15.23456 44.03387 moveto -(v) cmr10 9.96265 fshow --10.25327 44.03387 moveto -(erze) cmr10 9.96265 fshow -10.25323 44.03387 moveto -(1) cmr10 9.96265 fshow --2.85161 30.50577 moveto -(u) cmmi10 9.96265 fshow - 1 setlinecap -newpath 16.02676 -18.89763 moveto --16.02676 -18.89763 lineto stroke -newpath -12.3314 -17.36693 moveto --16.02676 -18.89763 lineto --12.3314 -20.42833 lineto - closepath -gsave fill grestore stroke -newpath -33.07086 47.24408 moveto --55.35715 39.70828 -70.35747 18.80147 -70.35747 -4.72441 curveto stroke -newpath -71.7532 -0.9763 moveto --71.3359 -2.23488 -70.87085 -3.48505 -70.35747 -4.72441 curveto --69.84409 -3.48505 -69.28891 -2.2722 -68.69403 -1.0872 curveto - closepath -gsave fill grestore stroke -newpath 33.07086 66.14172 moveto -56.41174 50.1016 70.35747 23.59666 70.35747 -4.72441 curveto stroke -newpath 68.74118 -1.06499 moveto -69.3066 -2.2687 69.84563 -3.48874 70.35747 -4.72441 curveto -70.86931 -3.48874 71.35088 -2.2449 71.80225 -0.99394 curveto - closepath -gsave fill grestore stroke -showpage -%%EOF -- 2.39.2