nejprve body z~obálky odebírat a $k$-tý bod pøidáme a¾ ve chvíli, kdy jeho
pøidání smìr zatáèení neporu¹í.
-\s{Algoritmus:}
-
-\algo
-
+\algo{KonvexníObal}
\:Setøídíme body podle $x$-ové souøadnice, oznaème body $b_1, \ldots, b_n$.
\:Vlo¾íme do horní a dolní obálky bod $b_1$: $H = D = (b_1)$.
\:Pro ka¾dý dal¹í bod $b = b_2,\ldots,b_n$:
\::::Odebereme poslední bod $h_k$ z~obálky $H$.
\:::Pøidáme bod $b$ do obálky $H$.
\::Symetricky pøepoèteme dolní obálku (s orientací doprava).
-\: Výsledný obal je tvoøen body v~obálkách $H$ a $D$.
-
+\:Výsledný obal je tvoøen body v~obálkách $H$ a $D$.
\endalgo
Rozebereme si èasovou slo¾itost algoritmu. Setøídit body podle $x$-ové souøadnice doká¾eme v~èase $\O(n \log n)$. Pøidání dal¹ího bodu do obálek
Algoritmus pro hledání prùnikù úseèek pak funguje následovnì:
-\s{Algoritmus:}
-
-\algo
-
+\algo{Prùseèíky}
\:$P \leftarrow \emptyset$.
\:Do $K$ vlo¾íme zaèátky a konce v¹ech úseèek.
\:Dokud $K \ne \emptyset$:
se rozhodneme, zda se vydat doleva nebo doprava.
Prùøez obsahuje v¾dy nejvý¹e~$n$ úseèek, tak¾e operace se stromem budou
-trvat $\O(\log n)$. V~kalendaøi se nachází nejvý¹e~$n$ zaèátkù a koncù
+trvat $\O(\log n)$. V~kalendáøi se nachází nejvý¹e~$n$ zaèátkù a koncù
a nejvý¹e~$n$ prùseèíkových událostí (ty plánujeme pro dvojice úseèek
sousedících v~prùøezu, a~tìch je v¾dy nejvý¹e~$n$). Operace s~kalendáøem
proto trvají také $\O(\log n)$.
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.
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.
+
+Voroného diagram pro $n$~zadaných bodù je tedy velký $\O(n)$. Dodejme, ¾e ho 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~ADS z~roku 2007/2008.}
místo toho si uká¾eme, jak v ji¾ spoèteném Voroného diagramu rychle hledat nejbli¾¹í body.
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
+Uka¾me si pro zaèátek øe¹ení bez pøedzpracování. Rovinu budeme zametat shora dolù vodorovnou pøímkou. 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é.
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
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
projects / ads2.git / blobdiff