8-geom2/8-geom2.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{8}{Geometrie vrací úder}{(sepsal Pavel Klavík)}
   4
   5 \>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
   6 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.
   7
   8 {\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
   9 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}
  10
  11 \h{Hledání prùseèíkù úseèek}
  12
  13 Zkusíme nejprve Eskymákùm vyøe¹it lokalizaci ledních medvìdù.
  14
  15 {\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í
  16 -- 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?}
  17
  18 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ì.
  19
  20 \bigskip
  21 \centerline{\epsfxsize=1.5in\epsfbox{8-geom2_0_bear.eps}\hskip 4em\epsfxsize2in\epsfbox{8-geom2_1_usecky.eps}}
  22 \smallskip
  23 \centerline{Problém Eskymákù: Kde v¹ude se køí¾í medvìdí trasy?}
  24 \bigskip
  25
  26 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ý
  27 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í
  28 úseèek mívá toti¾ prùseèíkù spí¹e po málu. Pro tento pøípad si uká¾eme podstatnì rychlej¹í algoritmus.
  29
  30 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
  31 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
  32 uká¾eme, jak se s tìmito pøípady vypoøádat.
  33
  34 Algoritmus funguje na principu zametání roviny, popsaném v minulé pøedná¹ce. Budeme posouvat vodorovnou pøímku odshora dolù. V¾dy, kdy¾ narazíme na
  35 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 zajímavého bodu.
  36
  37 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
  38 se objeví. Výskyty prùseèíkù budeme poèítat prùbì¾nì, jinak bychom celý problém nemuseli øe¹it.
  39
  40 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
  41 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
  42 udr¾ujeme, zda se jejich smìry nìkde protnou. Algoritmus pro hledání prùnikù úseèek funguje následovnì:
  43
  44 \s{Algoritmus:}
  45
  46 \algo
  47
  48 \:$P \leftarrow \emptyset$.
  49 \:Do $K$ vlo¾íme zaèátky a konce v¹ech úseèek.
  50 \:Dokud $K \ne \emptyset$:
  51 \::Odebereme nejvy¹¹í událost.
  52 \::Pokud je to zaèátek úseèky, zatøídíme novou úseèku do $P$.
  53 \::Pokud je to konec úseèky, odebereme úseèku z $P$.
  54 \::Pokud je to prùseèík, nahlásíme ho a prohodíme úseèky v $P$.
  55 \::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.
  56 \endalgo
  57
  58 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áø
  59 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
  60 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)$.
  61
  62 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¹í.
  63
  64 \h{Hledání nejbli¾¹ího bodu}
  65
  66 Nyní se pokusíme vyøe¹it i problém druhé strany.
  67
  68 {\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
  69 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!}
  70
  71 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
  72 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ì:
  73 $$B_i = \left\{y \in {\bb R}^2\ \vert\ \forall j:\rho(x_i,y) \le \rho(x_j,y)\right\}.$$
  74
  75 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
  76 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í,
  77 {\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
  78 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í.
  79 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
  80 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á
  81 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
  82 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
  83 optimalizaèních problémù. Dokázat v¹ak, ¾e tento problém le¾í v NP, není vùbec jednoduché.}
  84 Voroneho diagram je naznaèen na obrázku, oblasti $B_i$ jsou ohranièené èernými èárami.
  85
  86 \twofigures{8-geom2_2_polorovina.eps}{Body bli¾¹í k $a$ ne¾ $b$.}{1.25in}{8-geom2_3_voroneho_diagram.eps}{Voroneho diagram.}{2.5in}
  87
  88 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
  89 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
  90 $\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:
  91 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.
  92
  93 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
  94 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
  95 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
  96 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é
  97 body.
  98
  99 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
 100 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
 101 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
 102 hroznì pomalé.
 103
 104 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
 105 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
 106 kterém le¾í. Poté polo¾íme dotaz na pøíslu¹ný strom. Dotaz doká¾eme zodpovìdìt v èase $\O(\log n)$.
 107
 108 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é
 109 struktury. Pod perzistencí se myslí, ¾e struktura si umo¾òuje uchovávat svoji historii. Èásteènì perzistentní struktury nemohou svoji historii
 110 modifikovat.
 111
 112 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.
 113 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
 114 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
 115 $\O(k)$, prostì operace nemá tolik èasu, aby mohla pozmìnit pøíli¹ velikou èást stromu.
 116
 117 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
 118 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
 119 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í
 120 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
 121 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
 122 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á.
 123
 124 \bye