[ads2.git] / 6-geom / 6-geom.tex

\input lecnotes.tex

\prednaska{6}{Geometrické algoritmy}{}

\>Uká¾eme si nìkolik základních algoritmù na øe¹ení geometrických problémù v~rovinì. Proè zrovna v~rovinì? Inu, jednorozmìrné problémy bývají triviální
a naopak pro vy¹¹í dimenze jsou velice komplikované. Rovina je proto rozumným kompromisem mezi obtí¾ností a zajímavostí.

Celou kapitolou nás bude provázet pohádka ze ¾ivota ledních medvìdù. Pokusíme se vyøe¹it jejich \uv{ka¾dodenní} problémy~\dots

\h{Hledání konvexního obalu}

{\I Daleko na severu ¾ili lední medvìdi. Ve vodách tamního moøe byla hojnost ryb a jak je známo, ryby jsou oblíbenou pochoutkou ledních medvìdù.
Proto¾e medvìdi z~na¹í pohádky rozhodnì nejsou ledajací a ani chytrost jim neschází, rozhodli se v¹echny ryby pochytat. Znají pøesná místa výskytu
ryb a rádi by vyrobili obrovskou sí», do které by je v¹echny chytili. Pomozte medvìdùm zjistit, jaký nejmen¹í obvod taková sí» mù¾e mít.}

\figure{7-geom5_rybi_motivace.eps}{Problém ledních mìdvìdù: Jaký je nejmen¹í obvod sítì?}{3in}

Neboli v~øeèi matematické, chceme pro zadanou mno¾inu bodù v~rovinì nalézt její konvexní obal.

\s{Definice:} O~mno¾inì bodù øekneme, ¾e je {\I konvexní}, pokud pro ka¾dé dva body obsahuje i celou úseèku mezi nimi.
{\I Konvexní obal} dané mno¾iny bodù~$M$ je nejmen¹í konvexní mno¾ina, která obsahuje v¹echny body mno¾iny~$M$.%
\foot{Nejmen¹í myslíme vzhledem k~inkluzi, tedy je to prùnik v¹ech konvexních mno¾in
obsahujících v¹echny body z~$M$.
\endgraf
Pamatujete si na lineární obaly ve vektorových prostorech? Lineární obal
mno¾iny vektorù je nejmen¹í vektorový podprostor, který tyto vektory obsahuje.
Není náhoda, ¾e tato definice pøipomíná definici konvexního obalu. Na druhou
stranu ka¾dý vektor z~lineárního obalu lze vyjádøit jako lineární kombinaci
daných vektorù. Podobnì platí i pro konvexní obaly, ¾e ka¾dý bod z~obalu je
konvexní kombinací daných bodù. Ta se li¹í od lineární v~tom, ¾e v¹echny
koeficienty jsou v~intervalu $[0,1]$ a navíc souèet v¹ech koeficientù je $1$.
Tento algebraický pohled mù¾e mnohé vìci zjednodu¹it. Zkuste dokázat, ¾e obì
definice konvexního obalu jsou ekvivalentní.}

Snadno si v¹imneme, ¾e konvexní obal koneèné mno¾iny bodù je v¾dy nìjaký
konvexní mnohoúhelník. Navíc víme, ¾e vrcholy le¾í v~nìkterých ze~zadaných bodù.
Pro malé poèty bodù to bude vypadat následovnì:

\figure{7-geom1_male_obaly.eps}{Konvexní obaly malých mno¾in.}{3in}

Na¹ím úkolem tedy bude najít tento mnohoúhelník a vypsat na výstup
jeho vrcholy v~poøadí, ve~kterém na mnohoúhelníku le¾í (buï po~smìru hodinových
ruèièek nebo proti nìmu). Pro jednoduchost budeme konvexní obal øíkat pøímo tomuto
seznamu vrcholù.

Navíc budeme pøedpokládat, ¾e v¹echny body mají rùzné $x$-ové
souøadnice.\foot{To si mù¾eme dovolit pøedpokládat, nebo» se v¹emi body staèí
nepatrnì pootoèit. Tím konvexní obal urèitì nezmìníme a $x$-ové souøadnice
se ji¾ budou li¹it. Poøadí otoèených bodù podle $x$-ové souøadnice pøitom
odpovídá lexikografickému poøadí (druhotnì podle souøadnice~$y$)
pùvodních bodù. Tak¾e staèí v~na¹em algoritmu vymìnit tøídìní za~lexikografické
a bude fungovat obecnì.}
Tím máme zaji¹tìné, ¾e existují dva body, nejlevìj¹í a nejpravìj¹í, a~ty urèitì
le¾í na konvexním obalu.

Algoritmus na nalezení konvexního obalu funguje na principu, kterému se
obvykle øíká {\I zametání roviny}. Procházíme rovinu zleva doprava
(\uv{zametáme ji pøímkou}) a udr¾ujeme si konvexní obal tìch bodù, které jsme
u¾ pro¹li.

Na~poèátku máme konvexní obal jednobodové mno¾iny, co¾ je samotný bod.
Nech» tedy u¾ známe konvexní obal prvních $k-1$ bodù a chceme pøidat $k$-tý bod.
Ten urèitì na~novém konvexním obalu bude le¾et (je nejpravìj¹í), ale jeho pøidání
k~minulému obalu mù¾e zpùsobit, ¾e hranice pøestane být konvexní. To ale lze
snadno napravit -- staèí z~hranice odebírat body po~smìru a proti smìru hodinových ruèièek
tak dlouho, ne¾ opìt bude konvexní.

Napøíklad na~následujícím obrázku nemusíme po smìru hodinových ruèièek odebrat ani jeden
bod, obal je v poøádku. Naopak proti smìru ruèièek musíme odebrat dokonce dva body.

\figure{7-geom2_pridani_bodu.eps}{Pøidání bodu do konvexního obalu.}{4.5in}

Podle tohoto principu u¾ snadno vytvoøíme algoritmus. Aby se lépe popisoval,
rozdìlíme konvexní obal na {\I horní obálku} a {\I dolní obálku} -- to jsou
èásti, které vedou od~nejlevìj¹ího bodu k~nejpravìj¹ímu \uv{horem} a \uv{spodem}.

\figure{7-geom3_obalky.eps}{Horní a dolní obálka konvexního obalu.}{3.4in}

Obì obálky jsou lomené èáry, navíc horní obálka poøád zatáèí doprava a dolní
naopak doleva. Pro udr¾ování bodù v~obálkách staèí dva zásobníky. V~$k$-tém
kroku algoritmu pøidáme $k$-tý bod zvlá¹» do horní i dolní obálky. Pøidáním
$k$-tého bodu se v¹ak mù¾e poru¹it smìr, ve kterém obálka zatáèí. Proto budeme
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

\: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$:
\::Pøepoèítáme horní obálku:
\:::Dokud $\vert H\vert \ge 2$, $H = (\ldots, h_{k-1}, h_k)$ a úhel $h_{k-1} h_k b$ je orientovaný doleva:
\::::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$.

\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
trvá lineárnì vzhledem k~poètu odebraných bodù. Zde vyu¾ijeme obvyklý postup: Ka¾dý bod je odebrán nejvý¹e jednou, a tedy v¹echna odebrání trvají
dohromady $\O(n)$. Konvexní obal doká¾eme sestrojit v~èase $\O(n \log n)$, a pokud bychom mìli seznam bodù ji¾ utøídený, doká¾eme to dokonce v
$\O(n)$.

\s{Algebraický dodatek:} Jak zjistit orientaci úhlu? Uká¾eme si jednoduchý
zpùsob zalo¾ený na lineární algebøe. Budou se k~tomu hodit vlastnosti determinantu.
Absolutní hodnota determinantu je objem rovnobì¾nostìnu urèeného øádkovými
vektory matice. Dùle¾itìj¹í v¹ak je, ¾e znaménko determinantu urèuje
\uv{orientaci} vektorù -- zda je levotoèivá èi pravotoèivá. Proto¾e ná¹ problém
je rovinný, budeme uva¾ovat determinanty matic $2 \times 2$.

Uva¾me souøadnicový systém v~rovinì, jeho¾ $x$-ová souøadnice roste smìrem
doprava a~$y$-ová smìrem nahoru. Chceme zjistit orientaci úhlu $h_{k-1} h_k b$.
Oznaème $\vec u = (x_1, y_1)$ rozdíl souøadnic bodù $h_k$ a~$h_{k-1}$ a podobnì
$\vec v = (x_2, y_2)$ rozdíl souøadnic bodù $b$ a~$h_k$. Matici $M$ definujeme
následovnì: $$M = \pmatrix{\vec u \cr \vec v} = \pmatrix {x_1&y_1\cr
x_2&y_2}.$$ Úhel $h_{k-1} h_k b$ je orientován doleva, právì kdy¾ $\det
M = x_1y_2 - x_2y_1$ je nezáporný, a spoèítat hodnotu determinantu je
jednoduché. Mo¾né situace jsou nakresleny na obrázku. Poznamenejme, ¾e
k~podobnému vzorci se lze také dostat pøes vektorový souèin vektorù $\vec u$
a $\vec v$.

\figure{7-geom4_determinant.eps}{Jak vypadají determinanty rùzných znamének v~rovinì.}{4.6in}

\h{Rychlej¹í algoritmus}

Také vám vrtá hlavou, zda jde konvexní obal sestrojit rychleji? Obecnì ne,
alespoò pokud chceme body na konvexním obalu vydat v~poøadí, v~jakém se
na hranici nacházejí.\foot{Pak bychom toti¾ umìli tøídit reálná èísla
v~èase lep¹ím ne¾ $\Omega(n\log n)$, co¾ se ví, ¾e nejde (ná¹ dolní
odhad slo¾itosti tøídìní z~minulého semestru na~to ov¹em nestaèí).
Zkuste pøevod z~tøídìní na hledání konvexního obalu vymyslet sami.}
Pokud ov¹em na~konvexním obalu vìt¹ina bodù nele¾í, jde to rychleji.

Na pøedná¹ce to sice nebylo (a~u~zkou¹ky nebude), ale zde si uká¾eme nejrychlej¹í
známý algoritmus, jeho¾ autorem je T.~Chan a který funguje v~èase $\O(n \log h)$,
kde $h$ znaèí poèet bodù le¾ících na konvexním obalu. Pøekvapivì bude docela snadný.

Pøedpokládejme, ¾e bychom znali velikost konvexního obalu $h$. Rozdìlíme body
libovolnì do $\lceil n/h \rceil$ mno¾in $Q_1, \ldots, Q_k$ tak, aby
v~ka¾dé mno¾inì bylo nejvý¹e~$h$ bodù. Pro ka¾dou z~tìchto mno¾in nalezneme
konvexní obal pomocí vý¹e popsaného algoritmu. To doká¾eme pro jednu v~èase
$\O(h \log h)$ a pro v¹echny v~èase $\O(n \log h)$. V druhé fázi spustíme
tyto pøedpoèítané obaly slepíme do~jednoho pomocí tak zvaného {\I provázkového
algoritmu.} Ten se opírá o~následující pozorování:

\s{Pozorování:} Úseèka spojující dva body $a$ a $b$ le¾í na konvexním obalu,
právì kdy¾ v¹echny ostatní body le¾í na té¾e stranì pøímky prolo¾ené touto
úseèkou.

Algoritmu se øíká provázkový, proto¾e svojí èinností pøipomíná namotávání
provázku podél konvexního obalu.  Zaèneme s bodem, který na konvexním obalu
urèitì le¾í, to je tøeba ten nejlevìj¹í. V ka¾dém kroku nalezneme následující
bod po obvodu konvexního obalu. To udìláme napøíklad tak, ¾e projdeme v¹echny
body a vybereme ten, který svírá nejmen¹í úhel s poslední stranou konvexního
obalu. Novì pøidaná úseèka vyhovuje pozorování a proto do konvexního obalu
patøí. Po $h$ krocích se dostaneme zpìt k nejlevìj¹ímu bodu a výpoèet ukonèíme.
V ka¾dém kroku potøebujeme projít v¹echny body a vybrat následníka, co¾
doká¾eme v èase $\O(n)$. Celková slo¾itost algoritmu je tedy $\O(n \cdot h)$.

\twofigures{7-geom6_provazkovy_algoritmus.eps}{Provázkový algoritmus.}{1.25in}{7-geom7_naslednik_pres_konvexni_obal.eps}{Hledání kandidáta v pøedpoèítaném obalu.}{2.5in}

Provázkový algoritmus funguje, ale má jednu obrovskou nevýhodu -- je toti¾
ukrutnì pomalý. Ký¾eného zrychlení dosáhneme, pokud pou¾ijeme pøedpoèítané
konvexní obaly. Ty umo¾ní rychleji hledat následníka. Pro ka¾dou z mno¾in $Q_i$
najdeme zvlá¹» kandidáta a poté z nich vybereme toho nejlep¹ího. Mo¾ný kandidát
v¾dy le¾í na konvexním obalu mno¾iny $Q_i$. Vyu¾ijeme toho, ¾e body obalu jsou
\uv{uspoøádané}, i kdy¾ trochu netypicky do kruhu. Kandidáta mù¾eme hledat
metodou pùlení intervalu, jen detaily jsou malièko slo¾itìj¹í, ne¾ je
obvyklé. Jak pùlit, zjistíme podle smìru zatáèení konvexního obalu. Detaily si
rozmyslí ètenáø sám.

Èasová slo¾itost pùlení je $\O(\log h)$ pro jednu mno¾inu. Mno¾in je nejvý¹e
$\O({n \over h})$, tedy následující bod konvexního obalu nalezneme v èase
$\O({n \over h} \log h)$. Celý obal nalezneme ve slibovaném èase $\O(n \log
h)$. 

Popsanému algoritmu schází jedna dùle¾itá vìc: Ve skuteènosti vìt¹inou neznáme
velikost $h$. Budeme proto algoritmus iterovat s~rostoucí hodnotou $h$, dokud
konvexní obal nesestrojíme. Pokud pøi slepování konvexních obalù zjistíme, ¾e
konvexní obal je vìt¹í ne¾ $h$, výpoèet ukonèíme. Zbývá je¹tì zvolit, jak
rychle má $h$ rùst. Pokud by rostlo moc pomalu, budeme poèítat zbyteènì mnoho
fází, naopak pøi rychlém rùstu by nás poslední fáze mohla stát pøíli¹ mnoho.

V~$k$-té iteraci polo¾íme $h = 2^{2^k}$. Dostáváme celkovou slo¾itost
algoritmu: $$\sum_{m=0}^{\O(\log \log h)} \O(n \log 2^{2^m})
= \sum_{m=0}^{\O(\log \log h)} \O(n \cdot 2^m) = \O(n \log h),$$ kde poslední
rovnost dostaneme jako souèet prvních $\O(\log \log h)$ èlenù geometrické øady
$\sum 2^m$.

\h{Hledání prùseèíkù úseèek}

{\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 se svými
pøáteli rád schází. Av¹ak to je musí nejprve nalézt~\dots}

Zkusíme nejprve Eskymákùm vyøe¹it lokalizaci ledních medvìdù.

{\I Kdy¾ takový medvìd nemá co na práci, rád se prochází. Na místech, kde se trasy protínají, je zvý¹ená ¹ance, ¾e se dva medvìdi potkají a zapovídají
-- ostatnì co byste èekali od medvìdù. To jsou ta správná místa pro Eskymáka, který chce potkat medvìda. Jenom¾e jak tato køí¾ení najít?}

Pro zjednodu¹ení pøedpokládejme, ¾e medvìdi chodí po úseèkách tam a zpìt. Budeme tedy chtít nalézt v¹echny prùseèíky úseèek v rovinì.

\bigskip
\centerline{\epsfxsize=1.5in\epsfbox{8-geom2_0_bear.eps}\hskip 4em\epsfxsize2in\epsfbox{8-geom2_1_usecky.eps}}
\smallskip
\centerline{Problém Eskymákù: Kde v¹ude se køí¾í medvìdí trasy?}
\bigskip

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
uká¾eme, jak se s~tìmito pøípady vypoøádat.

Algoritmus funguje na principu zametání roviny, podobnì jako hledání konvexního
obalu. Budeme posouvat vodorovnou pøímku odshora dolù. V¾dy, kdy¾ narazíme na
nový prùnik, ohlásíme jeho výskyt. Samozøejmì spojité posouvání nahradíme
diskrétním a pøímku v¾dy posuneme do dal¹ího bodu, kde se nìco zajímavého
dìje.

Tím zajímavým jsou {\I zaèátky úseèek}, {\I konce úseèek} a {\I prùseèíky
úseèek}. Dohromady jim budeme øíkat {\I události.} Po~utøídìní známe pro první
dva typy událostí poøadí, v jakém se objeví. Prùseèíkové události budeme
objevovat prùbì¾nì.

V~ka¾dém kroku si pamatujeme {\I prùøez} $P$ -- posloupnost úseèek zrovna
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í. V~nìm budou naplánovány v¹echny zaèátky
a konce le¾ící pod zametací pøímkou. Navíc se pro ka¾dou dvojici úseèek podíváme,
zda se pod zametací pøímkou protnou, a~pokud ano, tak takový prùseèík také naplánujeme.
(Mohli bychom pøitom úseèky pova¾ovat za~polopøímky, fale¹né prùseèíky toti¾
beztak sma¾eme døíve, ne¾ na nì dojde øada.)

Algoritmus pro hledání prùnikù úseèek pak funguje následovnì:

\s{Algoritmus:}

\algo

\:$P \leftarrow \emptyset$.
\:Do $K$ vlo¾íme zaèátky a konce v¹ech úseèek.
\:Dokud $K \ne \emptyset$:
\::Odebereme nejvy¹¹í událost.
\::Pokud je to zaèátek úseèky, zatøídíme novou úseèku do $P$.
\::Pokud je to konec úseèky, odebereme úseèku z $P$.
\::Pokud je to prùseèík, nahlásíme ho a prohodíme úseèky v $P$.
\::Navíc v¾dy pøepoèítáme naplánované prùseèíkové události -- v¾dy maximálnì dvì odebereme a dvì nové pøidáme.
\endalgo

Zbývá rozmyslet, jaké datové struktury pou¾ijeme pro reprezentaci prùøezu a kalendáøe.
S~kalendáøem je to snadné, ten mù¾eme ulo¾it napøíklad do~haldy. Co potøebujeme dìlat
s~prùøezem? Vkládat a odebírat úseèky, ale také k~dané úseèce nalézt jejího pøedchùdce
a následníka (to je potøeba pøi plánování prùseèíkových událostí). Nabízí se vyu¾ít
vyhledávací strom, ov¹em jako klíèe v~nìm nemohou vystupovat $x$-ové souøadnice úseèek
(respektive jejich prùseèíkù se zametací pøímkou). Ty se toti¾ pøi ka¾dém posunutí
na¹eho \uv{ko¹tìte} mohou v¹echny zmìnit.

Ulo¾íme tedy do~vrcholù místo souøadnic jen odkazy na úseèky. Ty se nemìní (a~mezi
událostmi se nemìní ani jejich poøadí, co¾ je dùle¾ité) a kdykoliv nìjaká operace
se~stromem nav¹tíví jeho vrchol, dopoèítáme aktuální souøadnici úseèky a podle toho
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ù
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)$.

Pøi vyhodnocování ka¾dé události provedeme $\O(1)$ operací s~datovými
strukturami, tak¾e událost zpracujeme v~èase $\O(\log n)$. V¹ech událostí
dohromady je pøitom $\O(n+p)$, a~proto celý algoritmus dobìhne v~èase
$\O((n+p) \log n)$.

\s{Cvièení:} Popi¹te, jak algoritmus upravit, aby nepotøeboval pøedpoklad
obecné polohy úseèek. Podobnì jako u~konvexního obalu, i zde staèí jednoduché
úpravy.

Na závìr poznamenejme, ¾e existuje efektivnìj¹í, by» daleko komplikovanìj¹í,
algoritmus od Chazella dosahující èasové slo¾itosti $\O(n \log n + p)$.

\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.}

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$.

\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}

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.
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, èí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.
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.

\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 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}

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 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.

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}

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.

\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