1 ÚVOD
Úvod
Úloha lokalizace bodu spočívá v nalezení oblasti, v níž se nachází daný bod. Mějme například
mapu Evropy a místo na ní zadané pomocí zeměpisné šířky a délky. V takové situaci je
naším úkolem odpovědět na otázku, ve kterém státě ono místo leží. S řešením polohy bodu
se tedy setkáme u geografických informačních systémů (GIS). Dalšími praktickými aplikacemi
mohou být určování polohy místa kriminálního činu na mapě policejních okrsků nebo
neustálé zjišťování polohy lodi při mořeplavbě vzhledem k mělčinám a jiným nástrahám,
o nichž máme informace v mapě. Důležité je rovněž využití lokalizace bodu v počítačové
grafice, v počítačem podporovaném projektování (CAD) a v robotice. Potřeba znát polohu
bodu v různých odvětvích roste, ať už jako samostaný problém nebo jako dílčí problém
nějaké komplexnější úlohy, seznámíme se tedy v této práci s efektivním algoritmem.
Podobné problémy se vyskytovaly i v minulosti, proto již k úloze lokalizace bodu existuje
několik přístupů a různě efektivních algoritmů. K vyhledávacímu času O(log n) a paměťové
složitosti O(n) vedou čtyři zcela rozdílné postupy. Jedná se o řetězcovou metodu,
metodu zjemnění pomocí triangulace, metodu využívající persistentní vyhledávací stromy
a náhodnostní přírůstkovou metodu. Tato práce vychází z posledně jmenované, především
z algoritmu popsaného v [1], tedy z Mulmuleyova algoritmu [3] a Seidelovy prezentace [4].
Hlavními zdroji při zpracovávání dané problematiky byla jednak kniha [1], jednak přednáška
[2]. Některé informace pro čtvrtou kapitolu týkající se výpočetní složitosti byly čerpány
z [5]. Všechny příklady a obrázky byly pro účely této práce vytvořeny.
První kapitola se věnuje základním strukturám, s nimiž budeme pracovat, a základnímu
principu vyhledávání. Nejdříve popíšeme dvojitě souvislý seznam hran, což je systém tabulek
používaný k reprezentaci rovinných podrozdělění. Dále se zabýváme vhodnou úpravou
původně zadané mapy na lichoběžníkovou mapu, v níž se efektivněji vyhledává. Následně
popíšeme vyhledávací strukturu a obecný postup při vyhledávání.
V další kapitole se čtenář dočte o samotnému algoritmu, který je rozdělen na několik
dílčích částí, což dobře znázorňuje první pseudokód na straně 15. Kroky tohoto algoritmu
pak blíže rozebereme a jejich kostry opět zapíšeme v pseudokódech. Tímto čtenář získá
dobrou představu o tom, jak uvedený algoritmus naprogramovat.
V předchozím textu předpokládáme, že mapa, v níž hledáme, neobsahuje žádnou svislou
úsečku. Jinými slovy pracujeme pouze s případy, kdy každé dva body mají různé x-ové
souřadnice. Toto a další zjednodušení jsou učiněna kvůli snazšímu objasnění fungování
algoritmu. Třetí kapitola speciální případy rozebírá a uvádí postup, jak se s nimi vypořádat.
V poslední kapitole určíme, jaká je odhadovaná složitost uvedeného algoritmu. Od-
ÚVOD 2
hadneme časovou složitost vytvoření struktur pro vyhledávání, i velikost těchto struktur
a časovou složitost vyhledávání zadaného bodu, která je logaritmická.
Hlavní přínos této práce spočívá ve zjednodušení dvojitě souvislého seznamu pro potřeby
lokalizace bodu, v objasnění obecného postupu při vyhledávání v kapitole 1, v detailnějším
rozpisu jednotlivých kroků v kapitole 2, a to především kroků pátého a šestého,
které jsou v [1] uvedeny poměrně stručně a bez pseudokódu. Text je psán způsobem, který
má čtenáři přiblížit danou problematiku natolik, aby byl schopen podle uvedených postupů
a pseudokódů algoritmus řešící úlohu lokalizace bodu naprogramovat.
3 KAPITOLA 1. ZÁKLADNÍ KONSTRUKCE
Kapitola 1
Základní konstrukce
V této kapitole se blíže seznámíme s dvojitě souvislým seznamem hran, lichoběžníkovou
mapou a vyhledávací strukturou. První z nich reprezentuje rovinné podrozdělení, které je
na vstupu celé lokalizace. Potřebujeme tedy pochopit vlastnosti dvojitě souvislého seznamu
hran a naučit se s ním manipulovat. Druhá struktura vznikne úpravou původní mapy do
podoby, jež lépe vyhovuje požadavkům algoritmu. Odůvodníme zde formu této struktury
a na příkladech ukážeme, jak funguje. Poté si ukážeme, jak vypadá vyhledávací struktura.
Jedná se acyklický orientovaný graf, v němž procházíme od kořene k listům, které
mají vazbu na oblast příslušnou hledanému bodu. Nakonec si objasníme obecný postup
uplatňovaný při vyhledávání zadaného bodu.
1.1 Dvojitě souvislý seznam hran
Lokalizaci bodu provádíme v rovinném podrozdělení, tj. v určitém rozčlenění roviny na
menší oblasti, jejichž hranice tvoří libovolné mnohoúhelníky. Jedná se o orientovaný graf,
který nemusí být nutně souvislý.
v0
v1
v2
v5
e0,1
e7,8
e8,9e9,7 e5,2
Obrázek 1: Neorientovaná forma podrozdělení
1.1. DVOJITĚ SOUVISLÝ SEZNAM HRAN 4
Na obrázku 1 jsou uzly označeny jako v0, v1, v2, v5, hranami jsou e0,1 = (v0, v1) nebo
e5,2 = (v5, v2). Oblasti jsou dány hranami, jež tvoří jejich hranici, čili malý trojúhelník
uvnitř pětiúhelníku je určen množinou hran {e7,8, e8,9, e9,7}. Při práci s podrozdělením
považujeme hrany i oblasti za otevřené. Znamená to, že uzly nejsou prvkem žádné hrany,
stejně jako nepatří do žádné oblasti, a ani hrany nepatří do oblastí, které ohraničují. Nějaký
vztah však mezi uzly určujícími hranu a samotnou hranou je, říkáme tedy, že jsou sousední,
analogicky toto platí o dvojicích uzel-oblast a hrana-oblast.
Při uchovávání informací o mapě chceme šetřit místo a umět rychle vyhledat potřebná
data, ale zároveň chceme, abychom měli dostatek informací pro určité úkony. Můžeme například
potřebovat procházet hranici oblasti hranu po hraně nebo zjistit všechny hrany,
které sousedí s daným uzlem. Jako užitečné se ukazuje rozdělit každou hranu na dvě
opačně orientované hrany, označíme je slovem půlhrany. Odtud již lze opravdu reprezentovat
podrozdělení jako orientovaný graf. Původní obrázek se nám mírně změní:
v0
v1
v2
v5
e0,1
e7,8
e8,9
e9,7
e5,2
v3
v4
v6
v7
v8
v9
e1,0
e2,1
e1,2
e2,5
e8,7
f4
f2
f1
f3
Obrázek 2: Orientované rovinné podrozdělení
U hrany platilo, že měla dvě sousední oblasti, proto půlhrana má vždy právě jednu.
Půlhrany veďme tak, že jejich sousední oblasti se budou vždy nacházet po levé straně od
půlhrany, jdeme-li od jejího počátečního uzlu ve směru šipky. Tuto úmluvu již respektuje
i obrázek 2, viz výše. Dále vidíme, že každá půlhrana má jednoznačně určeného následníka
i předchůdce, takže budeme-li sledovat následníky určité půlhrany, projdeme po vnitřní
nebo vnější hranici její sousední oblasti. Tímto se dostáváme také k situaci oblastí, které
mohou mít dvě oddělené hranice (vnitřní a vnější) jako je tomu u oblasti f1 z obrázku
2. Nicméně i zde platí úmluva o poloze oblasti nalevo vůči svým hraničním půlhranám,
čili půlhrany vnější hranice míří proti směru hodinových ručiček, zatímco půlhrany vnitřní
hranice míří po směru hodinových ručiček.
Kompletní záznamy o uzlech, půlhranách a oblastech obsažené v tabulkách pak nazýváme
dvojitě souvislý seznam hran, viz tabulky:
5 KAPITOLA 1. ZÁKLADNÍ KONSTRUKCE
Uzel Souřadnice Vycházející půlhrana
v0 [0; 4] e0,1
v2 [7; 2] e2,5
v3 [9; 0] e3,2
v7 [2; 6] e7,8
...
...
...
Oblast Vnější hranice Vnitřní hranice
f1 e1,2 e8,9
f2 e3,4 nil
f3 e9,8 nil
f4 nil e6,5
...
...
...
Půlhrana Výchozí uzel Dvojče Sousední oblast Následník Předchůdce
e1,0 v1 e0,1 f4 e0,6 e2,1
e2,5 v2 e5,2 f1 e5,6 e1,2
e8,7 v8 e7,8 f3 e9,8 e7,9
e9,7 v9 e7,9 f1 e7,8 e8,9
...
...
...
...
...
...
Tabulky nám ukazují obecný dvojitě souvislý seznam hran. Záleží však na konkrétním
použití, zda všechny údaje tak, jak jsou zapsány, opravdu potřebujeme. Dokonce i některé
potřebné údaje lze uchovat úsporněji.
Podíváme-li se na tabulku s uzly, zjistíme, že dvojice uzel a z něj vedoucí půlhrana se
vyskytuje i v tabulce pro půlhrany, po řadě v druhém a prvním sloupci. Jelikož tabulka
uzlů nemá pro úlohu lokalizace bodu další uplatnění v podobě informací navíc, které by
obsahovala, můžeme ji zrušit. Zbývá pouze někde uložit souřadnice uzlů, což můžeme udělat
v tabulce půlhran ve sloupci Výchozí uzel.
V tabulce oblastí nelze zřejmě vypustit nic, navíc musíme počítat ještě s jedním sloupcem,
který bude obsahovat název oblasti. Tento název bude totiž konečným výstupem
lokalizace ve chvíli, kdy nalezneme oblast, v níž se daný bod nachází.
Poslední možnosti ušetření hledejme u půlhran, vhodné pojmenování nám velmi pomůže.
Podívejme se zpátky na obrázek 2 a všimněme si, že tam je každá půlhrana označena
vždy dvěma čísly, z nichž to první označuje výchozí uzel a to druhé uzel, kam půlhrana míří.
Ze sloupce Výchozí uzel tedy lze s klidným svědomím odejmout název uzlu - víme přeci, že
ei,j vychází z uzlu vi - a ponechat v něm jen souřadnice onoho uzlu. Sloupec Dvojče snadno
oželíme, víme-li, že dvojčetem k půlhraně ei,j bude vždy ej,i. Sloupce Sousední oblast a Následník
ponecháme v původní podobě. Konečně poslední sloupec také vynecháme, jelikož
přechůdce půlhrany lze zjistit pomocí sloupce Následník. Hledanou půlhranu najdeme ve
sloupci Následník a ve sloupci Půlhrana v příslušném řádku je onen hledaný předchůdce.
Zjednodušené tabulky pak vypadají takto:
Oblast Vnější hranice Vnitřní hranice
f1 e1,2 e8,9
f2 e3,4 nil
f3 e9,8 nil
f4 nil e6,5
1.2. LICHOBĚŽNÍKOVÁ MAPA T(S) 6
Půlhrana Výchozí uzel Sousední oblast Následník
e1,0 [3; 1] f4 e0,6
e2,5 [7; 2] f1 e5,6
e8,7 [5; 7] f3 e9,8
e9,7 [4; 3] f1 e7,8
...
...
...
...
Pro implementaci tabulek bych zde rád zdůraznil dvě věci, které nejsou z výše uvedených
příkladů patrné. Zaprvé namísto názvů půlhran a oblastí ve sloupcích Vnější hranice,
Vnitřní hranice, Sousední oblast a Následník používáme ukazatele, nikoliv proměnné. Zadruhé
každá oblast může mít několik podoblastí, čili sledováním následníků jedné půlhrany
nemusíme být schopni projít po celé vnitřní hranici její sousední oblasti. Ve sloupci Vnitřní
hranice proto musí být uvedena půlhrana pro každou podoblast dané oblasti.
1.2 Lichoběžníková mapa T(S)
Abychom se přiblížili vhodnému vyjádření zadané mapy začněme s jednoduchou strukturou.
Mějme nějaké rovinné podrozdělení S dané n hranami. Předpokládáme, že se tyto
hrany nekříží. Přesněji dvě různé hrany mají právě jeden nebo žádný společný sousední
uzel. Jinými slovy hrany se zde nikdy neprotínají, jsou vždy disjunktní.
Představme si podrozdělení S, abychom v něm mohli vyhledávat veďme každým uzlem
vertikálně přímku, viz obrázek 3. Máme-li zadán bod q, jehož polohu máme zjistit, postupujeme
následovně. Nejdříve se podíváme na jeho x-ovou souřadnici a porovnáme ji se
souřadnicemi jednotlivých uzlů, tím určíme, mezi kterými dvěma uzly se nachází. Dále již
prohledáváme jen pás určený těmito dvěma uzly. Tento pás obsahuje jen nekřížící se hrany,
proto je můžeme seřadit od nejnižší po nejvyšší. Bereme postupně jednotlivé hrany a vždy
se ptáme, zda je hledaný bod nad nebo pod ní. Takto se dostaneme do části podrozdělení,
která již přísluší jedné původní oblasti a její název je výsledkem hledání.
=
Obrázek 3
Vidíme, že takový systém vyhledávání funguje, problém však spočívá v přílišné velikosti
potřebné datové struktury. Vždyť podrozdělení S má až 2n uzlů, museli bychom tedy
7 KAPITOLA 1. ZÁKLADNÍ KONSTRUKCE
uchovávat informace až o 2n + 1 pásech, přičemž každý pás může obsahovat až n úseček.
Dohromady bychom získali kvadratickou složitost, což téměř znemožňuje použití takového
systému v praxi.
Myšlenka podobného hledání však není špatná. Potřebujeme ji jen upravit tak, aby
počet úseček nebyl o mnoho větší než v podrozdělení S. Pokoušíme se zde vlastně o zjemnění,
které usnadní vyhledávání, ale nezpůsobí příliš velký nárůst složitosti. Zkusme proto
každým uzlem vést vertikální přímku, která povede na obě strany jen tak daleko, dokud
se nedotkne již existující hrany, viz obrázek 4. O zjemnění se určitě jedná a v sekci 1.4. si
dokážeme, že skutečně nemá o mnoho větší složitost než původní podrozdělení S.
Učiňme nyní dvě zjednodušení, která nám usnadní práci. Prvním z nich bude vypořádání
se s neohraničenou oblastí, v níž se nachází všech n hran. Tato oblast může být
poměrně veliká, ale nám záleží pouze na tom, zda v ní bod leží, či nikoliv. Proto zavedeme
obdélník R obsahující všechny uzly. Cokoliv bude ležet vně tohoto obdélníku, patří do
neohraničené oblasti. Vnitřek obdélníka R podrobíme hlubšímu zkoumání. Druhé zjednodušení
již není tak snadno pochopitelné. Budeme předpokládat, že žádné dva uzly nemají
stejnou x-ovou souřadnici. V praxi se může stát, že toto často platit nebude. Nicméně pro
usnadnění pochopení následujících pasáží to nyní předpokládejme. V kapitole 3 ukážeme,
jak se problémové polohy bodů řeší.
Obrázek 4: Lichoběžníková mapa ohraničená obdélníkem R
Nyní již tedy máme lichoběžníkovou mapu, viz obrázek 4. Snadno lze vidět, že všechny
podoblasti v R jsou lichoběžníky (odtud ostatně název mapy), případně trojúhelníky. Na
trojúhelníky však lze pohlížet jako na degenerované lichoběžníky s jednou hranou délky
nula. Precizujme nyní samotné vytvoření lichoběžníkové mapy. Nechť S označuje množinu
všech hran obsažených v podrozdělení S. Pro odlišení S a S budeme prvkům množiny S
říkat úsečky a jejich koncovým uzlům body. Jak již víme, žádné dvě úsečky z S se nekříží
a všechny se nacházejí uvnitř obdélníka R. Navíc předpokládáme, že žádné dva různé
koncové body úseček z S nemají stejnou x-ovou souřadnici. Takové množině S pak říkáme
množina úseček v obecné poloze. Lichoběžníkovou mapu potom získáme vedením svislých
prodloužení oběma koncovými body každé úsečky v S. Horní svislé prodloužení i dolní
svislé prodloužení každého bodu vedou jen tak daleko, dokud se nestřetnou s jinou úsečkou
z S, popřípadě se stranou obdélníka R. Jelikož lichoběžníková mapa vzniká v závislosti na
množině S, značíme ji T(S).
1.3. JEDNOTLIVÉ LICHOBĚŽNÍKY 8
1.3 Jednotlivé lichoběžníky
Podívejme se nyní obecně na každý možný typ lichoběžníka, který se může v lichoběžníkové
mapě objevit. Každý lichoběžník  má jednu nebo dvě svislé strany a právě dvě strany,
které nejsou svislé. Označme top() a bottom() úsečky obsahující nesvislé strany .
Snadno odvodíme, že se vždy jedná o úsečky z S nebo o vodorovné strany obdélníka R.
Vertikální strany mohou být horním nebo dolním svislým prodloužením nebo svislou
stranou obdélníka R. Přesněji můžeme rozlišit pět různých situací pro levou stranu i pro
pravou stranu. Podívejme se tedy, jak může obecně vypadat levá svislá strana libovolného
lichoběžníka :
(a) Degeneruje do jednoho bodu, ten je zároveň levým koncovým bodem top() i bottom().
(b) Tvoří ji dolní svislé prodloužení levého koncového bodu top().
(c) Tvoří ji horní svislé prodloužení levého koncového bodu bottom().
(d) Skládá se z horního i dolního prodloužení bodu, který je pravým koncovým bodem
nějaké třetí úsečky.
(e) Rovná se levé svislé straně obdélníka R. Toto platí pro právě jeden lichoběžník v lichoběžníkové
mapě T(S) a to ten, který se nachází nejvíce vlevo.

 
(a) (b) (c) (d)
Výčet možných situací pro pravou svislou stranu je analogický. Ověřme si, že tyto
výčty jsou již úplné. Svislá strana nenulové délky původně v S žádná nebyla, protože
jsme předpokládali, že každé dva body měly různé x-ové souřadnice. Degenerovaná strana
je řešena v případě (a). Nenulová strana musela tedy vzniknout buď jako nějaké svislé
prodloužení (případy (b),(c) a (d)) nebo jako strana obdélníka R, který jsme přidali do
původní mapy, což postihuje přípac (e). Nic dalšího jsme k podrozdělení nepřidávali, proto
jinak svislá strana vzniknout nemohla a náš výčet je kompletní.
Lze si všimnout, že pro každý lichoběžník , vyjma toho nejvíce vlevo, je jeho levá
vertikální strana do určité míry určena jedním koncovým bodem p. Tento bod je buďto
levým koncovým bodem top() či bottom(), případně obou, nebo pravým koncovým
bodem třetí úsečky. Označíme jej leftp(), přičemž pro případ (e) definujeme jako leftp()
levý dolní vrchol obdélníka R. Obdobným způsobem definujeme rightp(). Pro každý
lichoběžník  tedy máme čtyři údaje, které jej jednoznačně určují: top(), bottom(),
leftp() a rightp().
9 KAPITOLA 1. ZÁKLADNÍ KONSTRUKCE
Zaveďme označení, že lichoběžník i je sousedem pro lichoběžník j a obráceně (tj.
vztah býti sousedem je symetrický) pokud i a j mají společnou svislou stranu a platí, že
top(i) = top(j) nebo bottom(i) = bottom(j). Bavíme-li se o množině úseček v obecné
poloze, pak má každý lichoběžník nejvýše čtyři takovéto sousedy. Konkrétně jim říkejme
levý horní soused, levý dolní soused, pravý horní soused a pravý dolní soused.
4
1
2
5
6
3
Obrázek 5
Na obrázku 5 vidíme, že 1 má pouze jednoho pravého souseda, a to pravého dolního,
kterým je 2. Lichoběžník 2 má naproti tomu dva levé sousedy, přičemž 1 je tím
horním a 5 tím dolním. Dobře si všimněte, že 4 nemá žádného pravého souseda a 5
nemá žádného levého souseda, což je způsobeno tím, že mají své vertikální strany v těchto
směrech degenerované.
1.4 Složitost T(S)
Když jsme si nyní předvedli, jak mohou lichoběžníky v T(S) obecně vypadat, můžeme
již ukázat, že složitost T(S) není o mnoho větší než složitost původního podrozdělení S.
Jinými slovy počet uzlů a lichoběžníků v T(S) závisí jen lineárně na počtu hran n.
Lemma 1. Lichoběžníková mapa T(S) množiny S, kterou tvoří n úseček v obecné poloze,
obsahuje nejvýše 6n + 4 uzlů a nejvýše 3n + 1 lichoběžníků.
Důkaz. Uzly v T(S) mohou být vrcholy obdélníka R, ty jsou 4. Dále se může jednat o koncové
body úseček z S, kterých je nejvýše 2n. A konečně to mohou být uzly, které vznikly
v místech, kde se horní a dolní svislá prodloužení koncových bodů dotýkají úseček z S
nebo stran obdélníka R. Jelikož koncových bodů v S je nejvýše 2n a z každého vedou dvě
prodloužení, je těchto nově vzniklých uzlů maximálně 2(2n). Celkem máme tedy nejvýše
4 + 2n + 2(2n) = 6n + 4 uzlů.
Počet možných lichoběžníků závisí na počtu uzlů. S ohledem na výčet všech možností,
jak může vypadat levá strana libovolného lichoběžníka, který jsme učinili v minulé sekci,
spočítejme lichoběžníky podle jejich leftp(). Každému lichoběžníku  zřejmě přísluší
právě jeden leftp(). Levý koncový bod úsečky může být leftp() nejvýše pro dva různé
1.5. VYHLEDÁVACÍ STRUKTURA D 10
lichoběžníky, viz případy (b) a (c). Pravý koncový bod je leftp() pro nejvýše jeden lichoběžník,
viz (d). Není ovšem příliš jasné, jestli to platí i u trojúhelníků jako v případě (a).
Na první pohled to vypadá, že jeden leftp() patří třem lichoběžníkům, ale uvědomme si, že
na místě levého vrcholu trojúhelníka se nachází dva body - levý koncový bod top() a levý
koncový bod bottom(), necháme proto bod z top() jako leftp() pro horní lichoběžník
a bod z bottom() jako leftp() pro dolní lichoběžník a trojúhelník. Trojúhelníky tedy
uvedené pravidlo také splňují. Jelikož máme n úseček, dostáváme tímto způsobem odhad
2n + n. Poslední možná situace, totiž (e) nastává pro právě jeden lichoběžník, a to ten
nejvíce vlevo, pro nějž je leftp() levý dolní vrchol obdélníka R. Dohromady proto T(S)
obsahuje maximálně 2n + n + 1 = 3n + 1 lichoběžníků.
Hraniční případ pro oba horní odhady, nastává tehdy, pokud se žádné dva uzly nepřekrývají,
viz obrázek 6. Pro n = 5 zde máme v lichoběžníkové mapě T(S) opravdu
6n + 4 = 34 uzlů a 3n + 1 = 16 lichoběžníků.
Obrázek 6
Taková situace sice v praxi těžko nastane, neboť pak bychom vyhledávali v mapě s pouze
jednou oblastí. Jelikož však používáme vyhledávací algoritmus ještě před samotným hledáním
zadaného bodu q, musíme i tuto situaci uvažovat. Při konstrukci vyhledávací struktury
(viz sekce 2.1) totiž do prázdné mapy postupně přidávámě jednotlivé úsečky.
1.5 Vyhledávací struktura D
Připomeňme, že na začátku dostaneme podrozdělení S. Pro lokalizaci bodu potřebujeme
vytvořit lichoběžníkovou mapu T(S) popsanou v sekci 1.2. a zároveň vyhledávací strukturu,
která by nám umožnila v T(S) efektivně vyhledávat. Nyní se tedy zaměřme na podobu
vyhledávací struktury D.
D je acyklický orientovaný graf s jedním kořenem, kde z každého vnitřního uzlu vedou
právě dvě hrany. Z koncových uzlů nevede žádná hrana, budeme je zde označovat slovem
listy. Vnitřní uzly v tomto grafu jsou dvojího typu a to x-ové uzly, které nesou názvy
koncového bodu nějaké úsečky z S, a y-ové uzly pojmenované úsečkou z S, kterou reprezentují.
V listech tohoto grafu se pak nalézají jednotlivé lichoběžníky z T(S). Pokud bude
11 KAPITOLA 1. ZÁKLADNÍ KONSTRUKCE
z kontextu jasné, že hovoříme o D, budeme někdy, kvůli větší srozumitelnosti, místo o uzlu
příslušejícímu bodu p (resp. úsečce s) mluvit o uzlu p (resp. s).
Při vyhledávání oblasti, v níž leží zadaný bod q, procházíme graf D od kořene k listům
a v každém x-ovém uzlu posuzujeme, zda hledaný bod leží napravo či nalevo od bodu
v x-ovém uzlu. V y-ových uzlech se ptáme, jestli q leží nad nebo pod danou úsečkou. Když
jsme v y-ovém uzlu grafu D, musíme se rovněž ujistit o tom, že pomyslná svislá přímka
procházející bodem q protíná úsečku, jejiž pojmenování tento uzel nese, jinak by totiž
otázka nad či pod postrádala smysl.
Jak jste si zajisté všimli, nevěnujeme se případům, kdy q leží na svislém prodloužení
nějakého bodu, ani případům, kdy se q nalézá přímo na některé z n úseček. Tyto výjimky
vyřešíme v následující sekci. Prozatím budeme předpokládat, že se q nalézá vždy uvnitř
nějakého lichoběžníka v T(S), proto popsané vyhledávání skončí vždy v některém z listů.
Datová struktuta D a lichoběžníková mapa T(S) jsou vzájemně propojeny. To znamená,
že každý list v D obsahuje ukazatel na lichoběžník v T(S), který reprezentuje a naopak.
Uveďme si nyní na příkladu vztahy mezi D a T(S):
A
B
C
D
E
F
G
H
I
J
Ks1
s2
s3
s4
s5p1
p2
p5
p4
p3
p5
p1
A p2
s1
B C
p3
s2
D s5
E F
s3
G s5
H F
p4
s4
s3
G I
J
K
Obrázek 7: Příklad lichoběžníkové mapy a jí příslušné vyhledávací struktury
1.6. POSTUP VYHLEDÁVÁNÍ BODU Q 12
Struktura D na obrázku 7 byla konstruována pro úsečky v pořadí s4, s1, s3, s2, s5. Graf
je orientován tak, že umístění nalevo či napravo od x-ových uzlů odpovídá jejich skutečné
poloze vůči bodům v těchto uzlech. Umístění nalevo od y-ového uzlu znamená polohu nad
danou úsečkou a umístění vpravo polohu pod úsečkou.
Každý x-ový uzel v D je na obrázku právě jednou. Toto platí obecně a odpovídá to
vyhledávání v pásech, jak bylo popsáno v sekci 1.2. Naproti tomu y-ové uzly se v D mohou
vyskytovat několikrát. Každý y-ový uzel se zřejmě v D vyskytuje alespoň jednou. Další
výskyt úsečky si je vždy způsoben tím, že na ní končí svislé prodloužení některého z koncových
bodů jiné úsečky, která se v pořadí úseček nachází před si. Například uzel s3 se v D
vyskytuje dvakrát. Na s3 totiž v lichoběžníkové mapě T(S) končí svislé prodloužení uzlu
p5, který je koncovým bodem úsečky s4, a ta se v pořadí úseček vyskytuje před s3. Bod p5
je navíc i koncovým bodem s5, ale ta se nachází v pořadí až za s3, což již další výskyt s3
nezpůsobí.
Listy odpovídající lichoběžníkům jsou na obrázku 7 z důvodu lepší přehlednosti grafu
uvedeny víckrát, viz lichoběžníky F a G. Znamená to, že v dané vyhledávací struktuře D
vede do takového listu více možných cest. V praxi je ale každý lichoběžník v D právě jednou,
pouze do něj mohou vést hrany z více vnitřních uzlů zároveň. Odtud také plyne, proč jsme
při definici D nepoužili pojmu strom, neboť se v těchto případech o strom nejedná.
Všimněme si rovněž toho, že úsečka si se v y-ovém uzlu v D objeví vždy až tehdy,
když na otázku, zda hledaný bod leží nad či pod si, lze jednoznačně odpovědět. Buďto se
v grafu nad uzlem s úsečkou si již vyskytují oba uzly odpovídající jejím koncovým bodům
(viz např. uzel s1), nebo se tam místo nich vyskytují uzly koncových bodů, které jsou
nad či pod úsečkou si a zároveň jsou ještě více vpravo (respektive více vlevo) než její levý
(respektive pravý) koncový bod. Tento druhý případ nastal u obou uzlů pro úsečku s3. Ten,
který se v grafu nachází více vpravo, má nad sebou uzel odpovídající jeho koncovému bodu
p4. Místo uzlu p3 zde však supluje uzel p5. Bod p5 je skutečně pod úsečkou s3 a zároveň
více vpravo než p3. Nalézáme-li se tedy v uzlu pro úsečku si pro jakékoliv i, nacházíme se
buď právě v pásu tvořeném jejími koncovými body, nebo v pásu ještě užším.
1.6 Postup vyhledávání bodu q
Vraťme se nyní k původní úloze lokalizace bodu. Na vstupu dostaneme rovinné podrozdělení
S v podobě dvojitě souvislého seznamu n hran a hledaný bod q. Dále dojde k vytvoření
lichoběžníkové mapy T(S) a datové struktury D pomocí algoritmu, který popíšeme v kapitole
2. Již na jeho začátku ověříme, zda hledaný bod náleží do obdélníka R. V případě, že
nikoliv, vyhledávání skončí s výsledkem, že bod q leží v neohraničené oblasti. Jestliže však
q  R, budeme procházet grafem D a posuzovat polohu bodu q vůči koncovým bodům
a úsečkám z S.
Jestliže bod q leží uvnitř nějakého lichoběžníka, vyhledávání dospěje do odpovídajícího
listu v D. Ve dvojitě souvislém seznamu hran máme pro každou půlhranu ei,j uveden
ukazatel na oblast, která se nachází nalevo od ní. Využijeme toho a všechny úsečky budeme
reprezentovat jako hrany orientované zleva doprava. Pro nalezený lichoběžník  v T(S)
13 KAPITOLA 1. ZÁKLADNÍ KONSTRUKCE
se tedy podíváme na oblast přilehlou k bottom(). Název této oblasti je potom finálním
výstupem lokalizace bodu q.
Shoduje-li se hledaný bod s některým z bodů lichoběžníkové mapy nebo leží uvnitř
některé ze zadaných úseček, výsledkem hledání může být skutečnost, že bod leží přímo
na původní mapě. V řadě aplikací ovšem takový výsledek nebude vyhovující, proto lze
v takovém případě bod q symbolicky posunout. Rovněž situace, kdy se bod q nachází
na některém ze svislých prodloužení, brání dokončení vyhledávání požadované oblasti.
Vyřešme nyní tyto tři komplikace.
Při procházení vyhledávací strukturou, se můžeme v x-ových uzlech ptát, zda q leží vlevo
od daného bodu, jestliže ne, pak pokračujeme automaticky doprava. Podobně v y-ových
uzlech zjistíme, jestli se q nachází nad úsečkou, když ne, postupujeme dolů. Symbolicky
tedy posouváme bod q doprava nebo dolů, případně oběma směry zároveň. Tímto zaručíme,
že vyhledávání pokaždé skončí v některém z lichoběžníků.
A
B
C
D
E
F
G
H
I
J
Ks1
s2
s3
s4
s5p1
p2
p5
p4
p3 = q2
q1 q3
p5
1,2,3
p1
1,2
A p2
1,2
s1
B C
p3
1,2
s2
1
D s5
1
E F
1
s3
2
G s5
2
H
2
F
p4
3
s4
3
s3
3
G I
3
J
K
Obrázek 8: Speciální polohy hledaného bodu q
1.6. POSTUP VYHLEDÁVÁNÍ BODU Q 14
Obrázek 8 ukazuje řešené tři případy, kdy q1 leží na úsečce, q2 se shoduje s jedním
z bodů a q3 se nachází uvnitř svislého prodloužení. Každému z hledaných bodů přísluší
v grafu D cesta, kterou při prohledávání procházíme. Pro každý bod qi, kde i  {1, 2, 3}
tedy projdeme postupně uzly označené i, uzel s velkým tučným číslem i znamená, že v něm
dojde k symbolickému posunutí podle výše definovaných pravidel.
Ověřme ještě, že takový postup zachová oblast, v níž se q nalézal. Leží-li q na svislém
prodloužení nějakého uzlu p, právě jednou (v uzlu p) posuneme q doprava. Víckrát se to
nemůže stát, neboť předpokládáme body s různými x-ovými souřadnicemi. Skončíme v
lichoběžníku, který má q na své levé straně. Jelikož q patřil svislému prodloužení, oblast
příslušející nalezenému lichoběžníku se rovná oblasti, do níž q patří. Nacházel-li se bod
q uvnitř úsečky s, při průchodu grafem D se jen jednou (v uzlu s) použije symbolické
posunutí dolů. Uzel s se sice ve vyhledávací struktuře může objevit víckrát, ale ne na cestě
k danému bodu q, odtud pouze jedno posunutí. Poloha q na úsečce znamená, že leží na
hranici dvou oblastí, nalezený lichoběžník bude patřit do jedné z nich, což je opět korektní.
Poslední případ kombinuje oba předchozí, když se q shoduje s koncovým bodem p úsečky
s. Zároveň tedy leží na svislém prodloužení i na úsečce, proto se obě uvedená posunutí
provedou, každé opět jen jednou. Výsledný lichoběžník bude jeden z těch, které mají bod
q na své hranici a který leží vpravo dole od bodu q. Jelikož se hledaný bod nacházel na
hranici několika oblastí, najdeme jednu z nich.
Uvedli jsme tedy celý postup od zadání ve formě podrozdělelní S až po nalezení oblasti,
který při lokalizaci bodu používáme. Výsledná oblast buď opravdu daný bod q obsahuje,
nebo q leží na její hranici.
15 KAPITOLA 2. NÁHODNOSTNÍ PŘÍRŮSTKOVÝ ALGORITMUS
Kapitola 2
Náhodnostní přírůstkový algoritmus
Uveďme pro úplnost, co značí jednotlivé charakteristiky algoritmu v názvu kapitoly. Označení
náhodnostní znamená, že uvnitř algoritmu figuruje princip náhody, v našem případě
náhodné uspořádání. Některá uspořádání nemusí vést k vytvoření dobré datové struktury.
S určitou pravděpodobností lze však předpokládat, že průměr přes všechny potenciální výsledky
uspořádání dobrý bude. Proto se také někdy používá označení pravděpodobnostní.
Algoritmus nazýváme přírůstkový, neboť se v jeho průběhu postupně přidávají jednotlivé
úsečky z množiny S. Vždy se tak vytvoří dočasná lichoběžníková mapa T a jí příslušná
vyhledávací struktura D. Teprve na závěr získáme konečnou podobu jak T(S) tak D.
2.1 Konstrukce D a T(S)
Uveďme nyní algoritmus, který současně vytvoří obě požadované struktury.
Algoritmus MAPA(S)
Vstup: Množina S navzájem se nekřížících n úseček
Výstup: Lichoběžníková mapa T(S) a k ní příslušející vyhledávací struktura D
1. Urči obdélník R tak, aby obsahoval všechny úsečky z S. Inicializuj lichoběžníkovou
mapu T a vyhledávací strukturu D.
2. Urči náhodné pořadí úseček s1, s2, . . . , sn z S.
3. for i  1 to n
4. do Najdi množinu lichoběžníků 0, 1, . . . , k v T, které úsečka si protíná ve
vnitřním bodě.
5. Z T odstraň 0, 1, . . . , k a nahraď je novými lichoběžníky, které vzniknou
přidáním úsečky si do T.
2.2. OBDÉLNÍK R A INICIALIZACE T A D 16
6. Z D odstraň listy příslušející lichoběžníkům 0, 1, . . . , k a vytvoř nové listy
pro nově vzniklé lichoběžníky v T. Propoj nové listy s již existujícími uzly
přidáním nových uzlů.
Tento algoritmus vytvoří obě požadované struktury. Podívejme se nyní podrobněji na
jeho jednotlivé kroky. Protože používáme přírůstkový algoritmus, zavedeme označení pro
množinu již přidaných úseček Si := {s1, s2, . . . , si}, přičemž klademe S0 := .
2.2 Obdélník R a inicializace T a D
Obdélník R určíme pomocí souřadnic jeho čtyř vrcholů Rld, Rpd, Rlh, Rph, kde Rld znamená
levý dolní vrchol, ostatní analogicky. V následujících přiřazeních [xi, yi] značí souřadnice
počátečního bodu i-té půlhrany. Funkcemi ceiling (resp. floor) máme na mysli horní celou
část daného čísla (resp. dolní celou část). Snadno se ověří, že tento výpočet zaručí, že
všechny body množiny S budou ležet uvnitř R.
xmin := min
i=1,...,2n
xi x1 := ceiling(xmin) - 1 Rld := [x1, y1]
xmax := max
i=1,...,2n
xi x2 := floor(xmax) + 1 Rpd := [x2, y1]
ymin := min
i=1,...,2n
yi y1 := ceiling(ymin) - 1 Rlh := [x1, y2]
ymax := max
i=1,...,2n
yi y2 := floor(ymax) + 1 Rph := [x2, y2]
V tomto momentě se zeptáme, zda hledaný bod q vůbec leží v obdélníku R, jestliže se
nachází na jeho hranici nebo vně, víme, že q náleží neohraničené oblasti a celý algoritmus
skončí. Pokud je uvnitř, pokračujeme dál. Množina úseček, se kterou nyní na počátku algoritmu
pracujeme je prázdná množina S0. Proto lichoběžníkovou mapu T(S0) tvoří pouze
obdélník R. Obdobně datová struktura D příslušná T(S0) obsahuje pouze jeden list, reprezentující
obdélník R.
2.3 Náhodné pořadí
Co se týče náhodného pořadí, předpokládáme existenci nějakého náhodného generátoru
čísel, nazveme jej RANDOM(k), který pro zadané celé číslo k určí náhodné číslo v rozmezí
od 1 do k. Potom použijeme následujícího algoritmu:
Algoritmus PERMUTACE(S)
Vstup: Uspořádaná množina n úseček {s1, s2, . . . , sn}
Výstup: Množina n úseček {s1, s2, . . . , sn} s náhodným pořadím
1. for k  n downto 2
2. do r  RANDOM(k)
3. Zaměň sk a sr.
17 KAPITOLA 2. NÁHODNOSTNÍ PŘÍRŮSTKOVÝ ALGORITMUS
2.4 Lichoběžníky protínané úsečkou si
Ve čtvrtém, pátém a šestém kroku algoritmu MAPA se přidává i-tá úsečka si a obě struktury
se poté aktualizují. Abychom věděli, kde všude se T a D změní, musíme nejprve
najít ty lichoběžníky, které přidávaná úsečka si protíná. Z předpokladu, že se úsečky nekříží
a z toho, že žádný koncový bod úsečky neleží uvnitř jiné úsečky, plyne, že úsečka si
může protínat pouze svislá prodloužení některých koncových bodů již přidaných úseček.
Seřadíme-li tedy protínané lichoběžníky 0, 1, . . . , k, stačí nalézt ten nejvíce vpravo
(k) či nejvíce vlevo (0) a skrze znalost levých (resp. pravých) sousedů určíme všechny
ostatní. My půjdeme cestou od levého koncového bodu si, proto hledejme 0. Jakmile
určíme j, tak pokud rightp(j) leží nad si, potom j+1 bude pravý dolní soused j,
v opačném případě se bude jednat o pravého horního souseda.
Pro nalezení lichoběžníka 0, nejprve potřebujeme zjistit polohu levého koncového bodu
úsečky si, nazvěme jej p. Pokud bod p dosud není přítomen v lichoběžníkové mapě T(Si-1)
(viz obrázek 9), použijeme pro jeho nalezení vyhledávací algoritmus. Lichoběžníková mapa
T(Si-1) a jí příslušná vyhledávací struktura D jsou již v této dílčí situaci použity. Vyhledávání
skončí v listu D, který přísluší hledanému lichoběžníku 0.
0
1
2
3
sip
Obrázek 9: Levý koncový bod přidávané úsečky dosud neležel v mapě T
Pokud je však bod p již součástí lichoběžníkové mapy T(Si-1) (viz obrázek 10), obdobné
vyhledávání neuspěje, neboť v nějakém x-ovém uzlu struktury D bod p nebude ležet ani
vpravo ani vlevo. Jelikož p je levým koncovým bodem, vyhledávání necháme pokračovat
doprava. Uvědomme si, že toto nastane pouze jednou, neboť předpokládáme body s různými
x-ovými souřadnicemi. Bod p je zároveň koncovým bodem nějaké úsečky s, která již
v T(Si-1) leží. V příslušném y-ovém uzlu, tedy bod p nebude ležet ani nad ani pod. Porovnáme
proto směrnice obou úseček. Označme pravý koncový bod úsečky si jako q = [qx, qy],
pravý koncový bod úsečky s jako r = [rx, ry] a souřadnice bodu p jako p = [px, py]. Pak
lichoběžník 0 leží
pod s je-li ry-py
rx-px
> qy-py
qx-px
(tj. úsečka s je strmější než si ).
nad s je-li ry-py
rx-px
< qy-py
qx-px
(tj. úsečka s je mírnější než si ).
Rovnost zřejmě nenastane, neboť si / Si-1, úsečky jsou navzájem různé a maximální
možný počet společných bodů - jedna - je již vyčerpán bodem p.
2.5. AKTUALIZACE T 18
si
p
1
0
Obrázek 10: Levý koncový bod přidávané úsečky již je součástí mapy T
Zbývá se pouze přesvědčit, že nerozhodná situace nemůže nastat nejprve v y-ovém uzlu.
Kdyby tomu tak bylo, v tu chvíli se pro nějakou úsečku s musíme nacházet v pásu určeném
jejími dvěma koncovými body nebo v nějakém ještě užším pásu. Jelikož hledáme bod p,
levá strana tohoto pásu musí být určena jím samotným. Kdyby byla určena bodem více
vpravo, vyhledávání by zřejmě do námi uvažovaného y-ového uzlu nedospělo. Protože se
nacházíme v pásu určeném p, tak se již uzel příslušný bodu p nutně nalézá v grafu na cestě,
po níž jsme do y-ového uzlu došli. Nerozhodná situace tedy nastala nejprve v x-ovém uzlu.
Jak vidíme, vyhledávání nakonec vždy dospěje do lichoběžníka 0, který se ze všech
lichoběžníků 0, 1, . . . , k nachází nejvíce vlevo. Z jeho znalosti již výše uvedeným postupem
získáme ostatní. Celkem lze čtvrtý krok algoritmu MAPA vyjádřit následovně:
Algoritmus SLEDUJ ÚSEČKU(T(Si-1),si)
Vstup: Lichoběžníková mapa T(Si-1) a přidávaná úsečka si
Výstup: Lichoběžníky 0, 1, . . . , k protínané úsečkou si
1. Označme levý a pravý koncový bod úsečky si jako pi a qi.
2. Proveďme vyhledávání ve struktuře D s bodem pi, abychom nalezli lichoběžník 0.
3. j  0;
4. while bod qi leží napravo od rightp(j)
5. do if rightp(j) leží nad si
6. then j+1 je pravý dolní soused j
7. else j+1 je pravý horní soused j
8. j  j + 1;
9. return 0, 1, . . . , k
2.5 Aktualizace T
Nyní si objasníme aktualizaci lichoběžníkové mapy po přidání úsečky si, tedy jak z T(Si-1)
vznikne T(Si). Levý a pravý koncový bod úsečky si pojmenujme po řadě pi a qi. Označme
si také nově přidávané lichoběžníky podle jejich polohy vzhledem k úsečce si. Lichoběžník
nalevo (resp. napravo) od úsečky, pokud takový existuje budeme značit Li (resp. Pi).
19 KAPITOLA 2. NÁHODNOSTNÍ PŘÍRŮSTKOVÝ ALGORITMUS
Lichoběžníky nad (resp. pod) nazvěme Hu
i (resp. Dv
i ), přičemž indexy u a v udávají pořadí
horních a dolních lichoběžníků.
Nejprve vyřešíme případ, kdy celá přidávaná úsečka leží uvnitř nějakého lichoběžníka,
viz obrázek 11. Tehdy je protínaným lichoběžníkem pouze 0. Levý lichoběžník Li má
stejný top, bottom a leftp jako 0, ale rightp(Li) = pi, podobně Pi se od 0 liší pouze
v tom, že leftp(Pi) = qi. Horní a dolní lichoběžník jsou také jednoznačně určeny pomocí si,
pi, qi a informací o 0.
=
Li
H1
i
D1
i
Pisi
0
pi
qi
Obrázek 11: Přidávaná úsečka leží celá uvnitř jednoho lichoběžníka
Dále si ukažme, jak algoritmus postupuje, v případě, kdy počet protínaných lichoběžníků
je více než jedna, tedy kdy k = 0, a zárověň oba koncové body úsečky již leží v lichoběžníkové
mapě, viz obrázek 12. Jelikož pi už nepřidáváme, žádný lichoběžník Li nevznikne.
Víme, ale že na místě 0 vzniknou H1
i a D1
i , snadno vypočteme jejich top, bottom i leftp,
tyto informace o nich zapíšeme a necháme pro tuto chvíli oba lichoběžníky ,,nedokončené .
Pro zjištění rightp potřebujeme vědět, jestli rightp(0) leží nad či pod úsečkou si, podle
toho rightp(H1
i ) := rightp(0) nebo rightp(D1
i ) := rightp(0). Stejný postup aplikujeme
i na další lichoběžníky 1, . . . , k-1. Poté všechny započaté lichoběžníky dokončíme přiřazeními
rightp(Hu
i ) := qi a rightp(Dv
i ) := qi. Nakonec podle přítomnosti či absence qi
v T(Si-1) určíme Pi, v našem případě tedy Pi nemáme.
H1
i
H2
i
H3
i
D1
i
D2
i
0
1
2
3
sipi qi pi qi
=
Obrázek 12: Přidávaná úsečka protíná více lichoběžníků
Pro aktualizaci lichoběžníkové mapy musíme uvažovat všechny možnosti polohy úsečky
si. Záleží na přítomnosti pi a qi v T(Si-1) a také na tom zda k = 0. V podobě pseudokódu
vypadá celý postup takto:
2.6. AKTUALIZACE D 20
Algoritmus AKTUALIZUJ MAPU(T(Si-1), si, 0, . . . , k)
Vstup: Lichoběžníková mapa T(Si-1), přidávaná úsečka si a množina lichoběžníků
0, 1, . . . , k protínaných úsečkou si
Výstup: Aktualizovaná lichoběžníková mapa T(Si)
1. u  1; v  1;
2. leftp(Hu
i )  pi; top(Hu
i )  top(0); bottom(Hu
i )  si;
3. leftp(Dv
i )  pi; top(Dv
i )  si; bottom(Dv
i )  bottom(0);
4. if pi / T(Si-1)
5. then leftp(Li)  leftp(0); top(Li)  top(0);
6. bottom(Li)  bottom(0); rightp(Li)  pi;
7. for j  0 to k - 1
8. do if rightp(j) leží nad si
9. then rightp(Hu
i )  rightp(j); u  u + 1;
10. leftp(Hu
i )  leftp(j+1); top(Hu
i )  top(j+1);
11. bottom(Hu
i )  si;
12. else rightp(Dv
i )  rightp(j); v  v + 1;
13. leftp(Dv
i )  leftp(j+1); top(Dv
i )  si;
14. bottom(Dv
i )  bottom(j+1);
15. rightp(Hu
i )  qi; rightp(Dv
i )  qi;
16. if qi / T(Si-1)
17. then leftp(Pi)  qi; top(Pi)  top(k);
18. bottom(Pi)  bottom(k); rightp(Pi)  rightp(k);
2.6 Aktualizace D
Současně s lichoběžníkovou mapou je potřeba změnit i jí odpovídající datovou strukturu
D(Si-1). Vraťme se k lichoběžníkové mapě na obrázku 11. List 0 zde musíme nahradit
malým stromem se dvěma x-ovými uzly pro pi a qi, jedním y-ovým uzlem pro si a čtyřmi
listy pro lichoběžníky, viz obrázek 13. Zde bychom čtenáře rádi upozornili na jedno pracovní
označení. Budeme zde používat sousloví nahradit stromem, což není úplně přesné. Ve
skutečnosti vždy přidáme všechny vnitřní uzly daného stromu, ale lichoběžníky přidáme
pouze tehdy, pokud se v D ještě nenacházejí. Jestliže už některý z lichoběžníků v D leží,
povedeme do něj pouze hranu, ale nevytvoříme jej znovu.
Naproti tomu v situaci znázorněné na obrázku 12 nemusíme vůbec přidávat x-ové uzly,
protože se již oba v D(Si-1) nacházejí. Stačí tedy každý protínaný lichoběžník nahradit
jedním y-ovým uzlem pro si a dvěma listy pro lichoběžníky. Abychom zjistili, které dva
lichoběžníky leží pro dané j nad a pod si, musíme pro j = 1, . . . , k - 1 určovat, jestli
rightp(j) leží nad nebo pod si. Pracujeme vždy s Hu
i a Dv
i , proto musíme vždy po nahrazení
lichoběžníka stromem zvýšit jeden z indexů u a v. Pokud se rightp(j) nachází
nad si, znamená to, že z rightp(j) vede svislé prodloužení, které ,,ukončuje lichoběžník
Hu
i a zároveň ,,otevírá Hu+1
i , proto zvýšíme u o jedna, v opačném případě postupujeme
21 KAPITOLA 2. NÁHODNOSTNÍ PŘÍRŮSTKOVÝ ALGORITMUS
D
0
= D
pi
Li qi
si
H1
i D1
i
Pi
1
Obrázek 13: Aktualizace vyhledávací struktury po změně mapy, viz obrázek 11
analogicky. První a poslední protínané lichoběžníky opět řešíme zvlášť, podle toho, jestli
pi a qi jsou již v T(Si-1).
Změnu datové struktury přidáním úsečky si z obrázku 12, znázorňuje obrázek 14. Ačkoliv
jsou však listy 0, 1, 2, 3 na obrázku nakresleny na stejné úrovni, v grafu D(Si-1)
mohou být hierarchicky různě vysoko. Při aktualizaci D tedy může docházet ke změnám
v celém grafu.
D
0 1 2 3
= D
si
H1
i D1
i
si
H2
i D1
i
si
H2
i D2
i
si
H3
i D2
i
Obrázek 14: Aktualizace vyhledávací struktury po změně mapy, viz obrázek 12
V průběhu aktualizace D(Si-1) se ptáme na stejné otázky a používáme stejné čítače
jako v algoritmu AKTUALIZUJ MAPU, proto se nabízí spojení obou dílčích algoritmů do
jednoho, pro lepší přehlednost však uvádíme oba pseudokódy zvlášť.
Algoritmus AKTUALIZUJ GRAF(D(Si-1), si, 0, . . . , k)
Vstup: Datová struktura D(Si-1), přidávaná úsečka si a množina lichoběžníků
0, 1, . . . , k protínaných úsečkou si
Výstup: Aktualizovaná datová struktura D(Si)
1. u  1; v  1;
2. if pi / T(Si-1)
3. then if qi / T(Si-1) and k = 0
4. then Nahraď list 0 stromem (a), viz obrázek 15.
5. else Nahraď list 0 stromem (b).
6. else if qi / T(Si-1) and k = 0
7. then Nahraď list 0 stromem (d).
8. else Nahraď list 0 stromem (c).
2.6. AKTUALIZACE D 22
9. for j  0 to k - 2
10. do if rightp(j) leží nad si
11. then u  u + 1;
12. else v  v + 1;
13. Nahraď list j+1 stromem (c).
14. if k = 0
15. then if rightp(k-1) leží nad si
16. then u  u + 1;
17. else v  v + 1;
18. if qi / T(Si-1)
19. then Nahraď list k stromem (d).
20. else Nahraď list k stromem (c).
pi
Li qi
si
Hu
i Dv
i
Pi
(a)
pi
Li si
Hu
i Dv
i
(b)
si
Hu
i Dv
i
(c)
qi
si
Hu
i Dv
i
Pi
(d)
Obrázek 15: Stromy, jimiž nahrazujeme změněné lichoběžníky
Probrali jsme tedy podrobněji jednotlivé kroky algoritmu MAPA, který pro zadanou
množinu úseček S zkonstruuje jednak lichoběžníkovou mapu T(S), jednak datovou strukturu
D potřebnou pro vyhledávání v ní.
23 KAPITOLA 3. SPECIÁLNÍ PŘÍPADY
Kapitola 3
Speciální případy
V předchozím textu jsme učinili zjednodušující předpoklad. Řekli jsme si, že budeme uvažovat
pouze množiny S, kde každé dva různé body mají různé x-ové souřadnice. Nyní
odbouráme nutnost tohoto předpokladu a zaručíme funkčnost algoritmu pro obecně libovolnou
množinu nekřížících se úseček S.
3.1 Různé x-ové souřadnice
Uvědomme si, že pro danou množinu S jsme volili vložení do systému souřadnic zcela
libovolně. Lze proto uvažovat o otočení souřadných os o dostatečně malý úhel tak, aby
se případné rovnosti souřadnic změnily v ostré nerovnosti. Bohužel takové otočení může
vést ke komplikacím. Jednak pokud máme na začátku za souřadnice čísla celá, případně
racionální s malým počtem desetinných míst, otočením výhodu snadnějšího a rychlejšího
počítání ztratíme, jednak se mohou objevit zaokrouhlovací chyby, tedy dva body s různými
x-ovými souřadnicemi, se mohou otočením v x-ových souřadnicích přiblížit natolik, že jejich
zaokrouhlení si již budou rovna.
Výhodnější je proto provádět odlišnou transformaci, a to jen symbolickou. Jelikož řešíme
pouze rovnost x-ových souřadnic, stačí použít afinní zobrazení podél x-ové osy. Říkejme
tomuto zobrazení šikmá transformace (anglicky shear transformation) a označme jej . Pro
malé  > 0 potom
 : [x, y]  [x + y, y] .
Z nezápornosti  plyne, že různé koncové body úseček z S := (s) | s  S budou
mít různé x-ové souřadnice. Navíc pro dostatečně malé  bude pro libovolné koncové body
p = [px, py] a r = [rx, ry] z S platit: px < rx = (p)x < (r)x. Požadované  lze zvolit
takto:
0 <  < min 1,
xj - xi
yi - yj
1  i  2n, 1  j  2n, xi < xj, yj < yi ,
kde [xi, yi] probíhá množinu koncových bodů úseček z S. Vidíme, že platí:
(p)x < (r)x  (px < rx)  (px = rx  py < ry) .
3.1. RŮZNÉ X-OVÉ SOUŘADNICE 24

y y
x x
1
Obrázek 16: Šikmá transformace 
Tedy uspořádání podle x-ové souřadnice po transformaci  je stejné jako lexikografické
uspořádání před transformací. Proto není potřeba počítat hodnotu , stačí uvažovat lexikografické
uspořádání bodů z S.
Zbývá se pouze přesvědčit, že ani ve druhém kroku algoritmu SLEDUJ ÚSEČKU (viz
popis na straně 17), kde porovnáváme směrnice dvou úseček, konkrétní  znát nepotřebujeme.
Mějme body p = [px, py], q = [qx, qy] a r = [rx, ry] takové, že úsečky pq a pr
nemají společný vnitřní bod a platí (p)x < (q)x a (p)x < (r)x. Potom skutečnost, že
směrnice (pq) < směrnice (pr) znamená:
1. pro px < qx a px < rx:
qy - py
qx - px + (qy - py)
<
ry - py
rx - px + (ry - py)
,
což je pro dostatečně malé  ekvivalentní s:
qy - py
qx - px
<
ry - py
rx - px
,
tedy směrnice(pq) < směrnice(pr)
2. pro px < qx, px = rx a py < ry:
qy - py
qx - px + (qy - py)
<
ry - py
(ry - py)
=
1

,
tedy jistě směrnice(pq) < .
Proto pro vhodné malé  je porovnání směrnic úseček (pq) a (pr) stejné jako porovnání
směrnic úseček pq a pr. Přitom pokud px = rx a py < ry, pak pokládáme
25 KAPITOLA 3. SPECIÁLNÍ PŘÍPADY
směrnice(pr) = . V případě, kdy směrnice (pq) > směrnice (pr) postupujeme naprosto
analogicky.
Zjistili jsme, že jediná změna v běhu algoritmu pro S spočívá v lexikografickém porovnání
bodů, když určujeme jejich pořadí podle x-ových souřadnic. Algoritmus sice konstruuje
lichoběžníkovou mapu pro S a datovou strukturu příslušnou T(S), ale samotnou
hodnotu  jsme nikde nepotřebovali znát, proto ani není nutné  na začátku počítat. Stačí
nám jen, že takové  splňující námi požadované podmínky, existuje.
3.2 Obecná poloha bodu q
Případy, kdy hledaný bod q leží na některém svislém prodloužení nebo na úsečce z S, jsme
již rozebrali v sekci 1.6., podívejme se však, co se změní použitím transformace .
Různé body jsou vždy transfomovány na body s různými x-ovými souřadnicemi. Bod
(q) proto bude ležet na transformovaném svislém prodloužení bodu (p) právě tehdy,
když platí q = p, což jsme již vyřešili. Vztah bodu a úsečky se zobrazením  také nezmění,
proto pro všechny úsečky s  S platí q  s  (q)  (s).
Všechny postupy, které jsme uváděli dříve lze tedy použít i na transformované úsečky
(si) a bod (q). Navíc zobrazení  má pouze symbolický charakter, a proto nemusíme
provádět další výpočty pro jeho realizaci.
4.1. VÝPOČETNÍ SLOŽITOST ALGORITMU MAPA 26
Kapitola 4
Odhady složitosti
V následující kapitole dokážeme, že algoritmus byl konstruován chytře, tzn. je poměrně
efektivní. Učiníme proto jisté odhady na časovou složitost konstrukce lichoběžníkové mapy
a vyhledávací struktury. Zjistíme, jakou přibližnou velikost bude mít vyhledávací struktura
D, a odhadneme časovou náročnost i samotného vyhledávání zadaného bodu q. Budeme
se tedy snažit odůvodnit, že naše volba náhodnostního algoritmu opravdu má deklarované
výhody.
Jak již bylo řečeno dříve náhodnost celého algoritmu MAPA spočívá v jeho druhém
kroku, kde generujeme náhodné pořadí úseček. Podíváme-li se na obrázek 7, dokážeme
něco říci o pořadí, podle něhož bylo D konstruováno. Předně první úsečka v tomto pořadí
musela být s4, neboť na začátku vždy vkládáme úsečku dovnitř do obdélníka R, čili prvním
přidávaným bodem je levý koncový bod první úsečky. Druhou úsečkou byla jistě s1. Nejsme
ovšem schopni určit, pořadí na třetím a čtvrtém místě, kde se nachází dvojice s2 a s3.
Vidíme tedy, že různá uspořádání mohou vést na stejnou datovou strukturu. Stejně dobře
ovšem pouhá záměna pořadí dvou úseček může zcela změnit D a tudíž potenciálně i délku
cesty, kterou musíme v grafu projít, abychom se dostali do lichoběžníka, v němž bod q leží.
4.1 Výpočetní složitost algoritmu MAPA
Obecně pracujeme s n! různými uspořádáními a také n! různými strukturami D. Přitom nás
zajímají uspořádání vedoucí na vyhledávací strukturu, která má malou složitost a krátký
vyhledávací čas. Uspořádání ovšem volíme náhodně, proto musíme počítat i s uspořádáními,
která nebudou vyhovovat těmto podmínkám. V této souvislosti se používá pojmů
očekávaná složitost nebo očekávaný vyhledávací čas, což znamená průměrnou složitost nebo
čas, kde se průměr počítá přes všech n! možných permutací prvků z S.
V praxi tedy mohou nastat případy, kdy vyhledávací struktura nebude pro dané pořadí
úseček dobrá, ale jejich podíl na celkovém počtu případů je vždy dostatečně malý. Ukažme
si nejprve, že očekávaný vyhledávací čas je O(log n).
27 KAPITOLA 4. ODHADY SLOŽITOSTI
Věta 2. Mějme datovou strukturu D zkonstruovanou algoritmem MAPA. Potom pro libovolný
bod q bude očekávaný vyhledávací čas O(log n).
Důkaz. Jelikož strukturu D již máme hotovou, rychlost vyhledávání záleží pouze na tom,
jak dlouhou cestu musíme v D projít. Z algoritmu AKTUALIZUJ MAPU na straně 21,
respektive z obrázku 15, je dobře patrné, že cesta se může v každém kroku algoritmu
prodloužit nejvýše o tři uzly. Odtud pro libovolný zadaný bod q platí, že nejdelší možná
cesta do tohoto bodu má délku 3n. Krokem algoritmu zde rozumíme provedení všech
příkazů pro dané i v cyklu FOR ve třetím kroku algoritmu MAPA.
Chceme-li ovšem zjistit průměrnou délku cesty přes všech n! možností, využijeme pravděpodobnost.
Mějme daný bod q a k němu cestu v D. Zřejmě každý uzel na této cestě byl
vytvořen v některém z n kroků algoritmu. Nechť pro i = 1, 2, . . . , n značí Xi náhodnou
veličinu, která udává počet uzlů na cestě k bodu q, jež byly vytvořeny v i-tém kroku algoritmu.
Jelikož Xi je opravdu náhodná veličina, neboť závisí pouze na pořadí úseček, platí
pro střední hodnoty následující:
E
n
i=1
Xi =
n
i=1
E[Xi].
Víme, že 0  Xi  3. Označme Pi pravděpodobnost, že v i-tém kroku byl vytvořen uzel
na cestě k bodu q. Potom pro i = 1, 2, . . . , n:
E[Xi]  3Pi.
Uvědomme si nyní, za jakých podmínek v i-tém kroku vznikne nový uzel na cestě ke q.
Stane se tak právě tehdy, když se lichoběžník obsahující bod q liší od lichoběžníku, který
q obsahoval v kroku předchozím. Jinými slovy nový uzel vznikne, pokud přidávaná i-tá
úsečka protne lichoběžník, v němž q dosud ležel. Označme lichoběžník obsahující bod q
v i-tém kroku symbolem q(Si). Uvedené pravděpodobnosti pak splňují
Pi = Pr[q(Si) = q(Si-1)] = Pr[q(Si) / T(Si-1)].
Platí-li nerovnost mezi lichoběžníky, pak byl q(Si) vytvořen při přidávání úsečky si.
Vzniklé lichoběžníky  budou mít na své hranici buď část úsečky si nebo alespoň její koncový
bod. Tedy top() nebo bottom() se bude rovnat si, případně leftp() či rightp()
bude jeden z koncových bodů si.
Nechť Si je libovolná podmnožina S. Pravděpodobnost, že se minimálně jeden z údajů
top(q(Si)), bottom(q(Si)), leftp(q(Si)) a rightp(q(Si)) bude lišit od příslušného údaje
pro q(Si-1) odpovídá pravděpodobnosti, že se v i-tém kroku prodlouží cesta k bodu
q. Lichoběžník q(Si) zůstane pro libovolnou permutaci úseček v Si vždy stále stejný,
může však být určen až čtyřmi různými úsečkami, přičemž extrémní případ zobrazuje
obrázek 17. Pořadí úseček v Si je náhodné, proto se všechny úsečky mohou vyskytnout
na i-tém místě se stejnou pravděpodobností. Úsečka l z obrázku 17 bude tedy poslední
v pořadí s pravděpodobností 1/i, stejnou pravděpodobnost mají i úsečky t, p a b. Tyto
4.1. VÝPOČETNÍ SLOŽITOST ALGORITMU MAPA 28
t
p
b
l q(Si)
Obrázek 17: Lichoběžník určený čtyřmi úsečkami
pravděpodobnosti sice mohou být závislé, neboť na určení některých lichoběžníků stačí
pouze dvě úsečky, ale my potřebujeme horní odhad. Je-li na i-tém místě jedna z úseček
určujících q(Si), dojde k prodloužení cesty k bodu q. Dohromady proto dostáváme:
Pi  4/i.
Poskládáme-li všechny uvedené rovnosti a nerovnosti, obdržíme horní odhad očekávaného
vyhledávacího času:
E
n
i=1
Xi 
n
i=1
3Pi 
n
i=1
12
i
= 12
n
i=1
1
i
= 12Hn.
V tomto případě Hn znamená n-té harmonické číslo:
Hn :=
1
1
+
1
2
+
1
3
+    +
1
n
.
Pokud máme n > 1, pak pro harmonická čísla Hn také platí následující nerovnost:
ln n < Hn < ln n + 1. (4.1)
Z druhé části nerovnosti 4.1 vidíme, že očekávaný vyhledávací čas je skutečně O(log n),
zatímco první nerovnost říká, že tento odhad není zbytečně nadhodnocený. Nerovnost plyne
ze vztahu mezi
n
1
1
x
dx = ln x a n
i=1
1
x
= Hn. Platí totiž Hn - 1 <
n
1
1
x
dx < Hn-1, kde
Hn - 1 a Hn-1 jsou po řadě dolní a horní integrální součet, viz obrázek 18.
y
xO 1 2 3 4 5 6 7
Obrázek 18: Integrální součty funkce 1/x na intervalu od 1 do 7
29 KAPITOLA 4. ODHADY SLOŽITOSTI
Věta 3. Očekávaná velikost datové struktury D je O(n).
Důkaz. Podobně jako v předchozím důkazu, závisí odhad na nějaké veličině. Zde se jedná
o počet uzlů, který stačí odhadnout, abychom zjistili přibližnou velikost D.
Jak jsme již uvedli dříve D obsahuje dva typy uzlů: listy, které přímo korespondují
s lichoběžníky v T(S) (tj. každý lichoběžník se v D vyskytuje právě jednou), a vnitřní uzly,
jimž odpovídají úsečky z S a jejich koncové body. Počet listů je dle Lemmatu 1 nejvýše
3n + 1, tedy O(n), zbývá odhadnout kolik vnitřních uzlů bude v D obsaženo.
Nechť ui označuje počet lichoběžníků vytvořených v i-té iteraci algoritmu, respektive
počet nově vzniklých listů v D. Potom nových vnitřních uzlů bude v i-té iteraci právě
ui - 1. Dokažme to indukcí vůči počtu lichoběžníků, které jsou přidáním úsečky si protnuty
a k jejichž nahrazení v i-té iteraci dochází. Je-li protnut jeden lichoběžník, pak na
obrázku 15 (viz strana 22) vidíme, že ve všech případech je počet vnitřních uzlů právě o
jedna menší než počet listů v D, tedy tvrzení platí. Předpokládejme, že jsme již uvedené
dokázali pro n protínaných lichoběžníků a mějme nyní úsečku protínající n + 1 lichoběžníků.
Veďme pomocnou svislou přímku některým z vrcholů protínaných lichoběžníků tak,
abychom protnuli úsečku si a rozdělili lichoběžníky na dvě skupiny (viz obrázek 19).
Obrázek 19: Rozdělení protínaných lichoběžníků na dvě skupiny
V levé skupině mějme nyní u lichoběžníků a v pravé v lichoběžníků. Všimněme si, že
jeden lichoběžník počítáme dvakrát, neboť pomocná přímka jej rozděluje. (Rozmyslete si,
že takový lichoběžník vždy existuje a je právě jeden.) Jelikož u < n a v < n, tak podle
předpokladu vznikne u - 1 a v - 1 nových vnitřních uzlů, celkem tedy (u - 1) + (v - 1) =
u + v - 2. Když si uvědomíme dvakrát počítaný lichoběžník, tak v i-té iteraci vznikne
u + v - 1 lichoběžníků a nových vnitřních uzlů tudíž máme skutečně o jedna méně. Tímto
je vztah mezi počtem nových vnitřních uzlů a nových listů v D dokázán.
Očekávaná velikost D se proto, s využitím nezávislosti hodnot ui - 1, rovná
O(n) + E
n
i=1
(ui - 1) = O(n) +
n
i=1
E[ui].
4.1. VÝPOČETNÍ SLOŽITOST ALGORITMU MAPA 30
Dále již potřebujeme jen shora ohraničit číslo ui pro i = 1, 2, . . . , n. Zafixujme si tedy
znovu libovolnou Si  S a definujme novou veličinu  pro každý lichoběžník   T(Si)
a úsečku s  Si:
(, s) :=
1 jestliže lichoběžník  vznikl přidáním úsečky s do T(Si-1).
0 jinak.
Už v předchozím důkazu jsme zjistili, že každý lichoběžník je určen nejvýše čtyřmi úsečkami.
Pro pevně daný lichoběžník  proto existují maximálně čtyři možné úsečky s, pro
něž by se (, s) = 1. Počet nově vzniklých lichoběžníků v T(Si) zároveň bude nejvýše
počet všech lichoběžníků v T(Si), který je z Lemmatu 1 O(i). Dostáváme tedy nerovnost:
sSi T(Si)
(, s)  4|T(Si)| = O(i),
tzn. sečteme-li počet všech lichoběžníků, které mohly vzniknout v i-tém kroku, bude jich
nejvýše O(i).
Počet lichoběžníků vzniklých přidáním úsečky si  Si je ui. Protože pořadí úseček v Si
generujeme náhodně, očekávanou hodnotu ui určíme pomocí průměru přes všechny s  Si:
E[ui] =
1
i sSi T(Si)
(, s) 
O(i)
i
= O(1).
Odvodili jsme, že v každém kroku algoritmu vznikne očekávaný počet O(1) nových lichoběžníků,
tedy i O(1) nových vnitřních uzlů v D. Spolu s již určeným počtem listů v D
máme proto očekávanou velikost O(n), neboť
O(n) +
n
i=1
E[ui]  O(n) +
n
i=1
O(1) = O(n) + O(n) = O(n).
Věta 4. Nechť S je množina n úseček v obecné poloze. Pak algoritmus MAPA vytvoří lichoběžníkovou
mapu T(S) a jí příslušnou datovou strukturu D v očekávaném čase O(n log n).
Důkaz. Díky dokázaným větám, máme nyní situaci již poměrně snadnou. První dva kroky
algoritmu MAPA mají složitost pouze O(n), neboť výpočet minim či maxim stejně jako
změnu pořadí lze reprezentovat jako nezávislé FOR cykly délky n. Třetí krok znázorňuje
suma pro i = 1, . . . , n. Ve čtvrtém kroku je nejnáročnější lokalizace levého koncového bodu
úsečky si v T(Si-1), která z Věty 2 proběhne v očekávaném čase O(log i). Pro odhadnutí
složitosti pátého a šestého kroku využijeme očekávaný počet nových lichoběžníků a vnitřních
uzlů E[ui]. Z toho plyne celková složitost algoritmu MAPA:
O(n) +
n
i=1
O(log i) + O(E[ui]) =
n
i=1
O(log i)  O(n log n).
Všimněme si, že očekávání v uvedených větách znamenalo průměrování přes všechna
možná uspořádání úseček, nezáleželo ovšem vůbec na konkrétních úsečkách nebo na hledaném
bodě q. Celý algoritmus tedy provede lokalizaci libovolného daného bodu v jakémkoliv
podrozdělení S v očekávaném čase O(n log n).
31 LITERATURA
Literatura
[1] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry:
Algorithms and Applications, Springer-Verlag, Third Edition, 2008.
[2] M. Čadek, Přednáška Geometrické algoritmy, PřF MU, podzim 2008.
[3] K. Mulmuley, A fast planar partition algorithm, I., Journal of Symbolic Computation,
10:253-280, 1990.
[4] R. Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal
decompositions and for triangulating polygons, Comput. Geom. Theory Appl.,
1:51-64, 1991.
[5] H. S. Wilf, Algorithms and Complexity, 1994, http://www.math.upenn.edu/~wilf/
AlgoComp.pdf, květen 2009.