% 10-tá kapitola
\documentclass[12pt,a4paper]{amsart}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}

\textwidth=154mm
\hoffset=-14mm

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{esvect}

\theoremstyle{plain}
\newtheorem{thm}{Věta}[section]
\newtheorem{cor}[thm]{Důsledek}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ap}[thm]{Appendix}

\theoremstyle{definition}
\newtheorem*{definition}{Definice}
\newtheorem{remark}[thm]{Poznámka}  
\newtheorem{example}[thm]{Příklad}
\newtheorem*{ack}{Acknowledgement}

\def\next{\operatorname{next}}
\def\prev{\operatorname{prev}}
\def\pj{p_{-1}}
\def\pd{p_{-2}}

\begin{document}

  


\setcounter{section}{9}
\section{\large Delaunayova triangulace}

\subsection*{Motivace.}
Uvažujme funkci $f:\mathbb R^2\to \mathbb R$. Její hodnoty známe pouze v konečné množině bodů $P$. Jeden způsob, jak takovou funkci aproximovat, je rozdělit konvexní obal  množiny $P$ na trojúhelníky s vrcholy v  bodech množiny $P$ a na těchto trojúhelnících aproximovat funkci $f$ lineárně.
To znamená následující: Každý bod $x$ trojúhelníka $p_i p_j p_k$ je konvexní kombinací bodů $p_i$, $p_j$, $p_k$
$$x=t_1p_1+t_2p_2+t_3p_3, \quad \text{ kde }t_1+t_2+t_3=1,\ t_1\ge 0, \ t_2\ge 0,\ t_3\ge 0,$$
a proto položíme
$$f(x)=t_1f(p_1)+t_2f(p_2)+t_3f(p_3).$$
Graf aproximace funkce $f$ je tedy tvořen v $\mathbb R^2\times \mathbb R$ trojúhelníky s vrcholy $(p_i,f(p_i)$, $(p_j,f(p_j)$ a $(p_k,f(p_k))$.
\vskip .5cm

OBR 10.1  Lineární aproximace funkce $f$

\vskip .5cm
Tato aproximace podstatně závisí na tom, jakým způsobem provedeme triangulaci konvexního obalu naší množiny. Zdá se, že dobrá triangulace je taková, kde nejsou trojúhelníky a malými úhly. Takovým triangulacím se budeme věnovat v následujícím textu.

\subsection*{Úhlově optimální triangulace}
Nejdříve ukážeme, že pro danou konečnou množinu $P$ bodů v rovině mají všechny triangulace jejího konvexního obalu stejný počet trojúhel\-ní\-ků. To nám dá možnost porovnávat různé triangulace lexikograficky podle velikosti úhlů.

\begin{thm} Nechť $P$ je množina $n$ bodů v rovině. Nechť konvexní obal množiny $P$ má $k$ hran. Potom je každá triangulace konvexního obalu tvořena $2n-2-k$ trojúhelníky a má $3n-3-k$ hran. 
\end{thm}

\begin{proof} Označme počet trojúhelníků v triangulaci jako $m$. Každý trojúhelník má tři hrany. Ze všech hran je $k$ hranou pouze jednoho trojúhelníku, zbývající jsou hranou právě dvou trojúhelníků. Celkový počet hran je tedy roven
$$h=\frac{3m+k}{2}.$$
Eulerova věta říká, že
$$n-h+(m+1)=2.$$
Dosazením za $h$ odvodíme po krátké úpravě
$$m=2n-2-k.$$
Odtud dosazením do výrazu pro $h$ dostaneme
$$h=3n-3-k.$$
\end{proof}

Nechť je tedy $\mathcal T$ nějaká triangulace množiny $P$ s $m=2n-2-k$ trojúhelníky. Trojúhelníky této triangulace mají $3m$ úhlů. Seřaďme je podle velikosti do posloupnosti
$$\alpha(\mathcal T)=(\alpha_1, \alpha_2,\dots,\alpha_{3m}), \quad 
\alpha_1\le \alpha_2\le \dots \le \alpha_{3m}.$$
Na těchto posloupnostech úhlů definujme lexikografické uspořádání
$$\alpha(\mathcal T)<\alpha(\mathcal T'),$$
jestliže existuje $i\in\{1,2,\dots,3m\}$ tak, že
$$\alpha_j=\alpha'_j \quad \text{ pro }j<i \quad \text{ a }\quad \alpha_i<\alpha'_i.$$
Triangulace $\mathcal T$ se nazývá {\it úhlově optimální}, jestliže je maximální v tomto uspořádání.


\subsection*{Legální hrany a legální triangulace}
Pro účely našeho algoritmu na vytváření vhodné triangulace budeme potřebovat pojem {\it legální hrany} a {\it legální triangulace}.
Před tím, než je budeme definovat, si krátce zopakujme to, co ze středoškolské geometrie víme o obvodových úhlech.

Na kružnici $\mathcal K$ se středem $s$ uvažujme body $p$ a $q$. Ty rozdělují kružnici na dva oblouky. Na jednom z nich zvolme bod $a$, na druhém bod
$b$. Úhly v trojúhelnících $pqa$ a $pqb$ u vrcholů $a$ a $b$ označme postupně jako $\alpha$ a $\beta$. Nazýváme je {\it obvodovými úhly} tětivy $pq$ pro jednotlivé oblouky kružnice $\mathcal K$. Obvodové úhly mají tyto dvě důležité vlastnosti:
\begin{itemize}
\item Velikost úhlů $\alpha$ a $\beta$ nezávisí na poloze bodů $a$ a $b$ v daných obloucích.
\item Součet $\alpha+\beta=180^o$.
\end{itemize}
Odtud lze snadno odvodit, že každý trojúhelník $pqc$, kde bod $c$ leží v polorovině $pqa$ uvnitř kružnice $\mathcal K$, má u vrcholu $c$ úhel
$$\gamma>\alpha$$
a každý trojúhelník $pqd$, kde bod $d$ leží v polorovině $pqa$ vně kružnice $\mathcal K$, má u vrcholu $d$ úhel
$$\delta<\alpha.$$
\vskip 0.5cm

OBR 10.2 Obvodové úhly
\vskip 0.5cm

Dále lze z vlastností obvodových úhlů ukázat, že čtyřúhelníku lze opsat kružnici, právě když má součet protilehlých úhlů roven $180^o$.

Nyní uvažujme triangulaci $\mathcal T$ a v ní hranu $pq$, která má v triangulaci $\mathcal T$ dva přilehlé trojúhelníky, a to $pqr$ a $pqt$. Takovou hranu nazveme {\it ilegální hranou triangulace} $\mathcal T$, jestliže bod $t$ leží uvnitř kružnice opsané trojúhelníku $pqr$. To je ekvivalentní s tím, že součet úhlů při vrcholech $r$ a $t$ obou trojúhelníků je větší než $180^o$ a tedy také s tím, že bod $r$ leží uvnitř kružnice opsané trojúhelníku $pqt$.
\vskip 0.5cm

OBR 10.3 Ilegální hrana $pq$
\vskip 0.5cm

Hrany triangulace $\mathcal T$, které nejsou ilegální nazýváme {\it legální}
a triangulaci bez ilegálních hran nazýváme {\it legální triangulací}.
Bezprostředním důsledkem této definice je následující charakterizace legální triangulace:

\begin{lemma}\label{legal} Triangulace je legální, právě když pro každou hranu $pq$ s přilehlými trojúhelníky $pqr$ a $pqt$ neleží bod $t$ uvnitř kružnice opsané trojúhelníku $pqr$.
\end{lemma}

Zásadní význam pro náš algoritmus má následující tvr\-ze\-ní.

\begin{lemma} Nechť $\mathcal T$ je triangulace s ilegální hranou $pq$,
která má v $\mathcal T$ přilehlé trojúhelníky $pqr$ a $pqt$. Vytvořme z triangulace $\mathcal T$ novou triangulaci $\mathcal T'$ tak, že hranu $pq$ nahradíme hranou $rt$. Tato hrana bude v triangulaci $\mathcal T'$ legální
a navíc v uspořádání definovaném v předchozím paragrafu bude
$$\alpha(\mathcal T)<\alpha(\mathcal T').$$
Výše uvedená výměna hrany $pq$ za $rt$ se nazývá {\it flipem}.  
\end{lemma}

\vskip 0.5cm

OBR 10.4 Flip
\vskip 0.5cm
 
\begin{proof} Protože hrana $pq$ je ilegální hranou triangulace $\mathcal T$, je součet úhlů u vrcholů $r$ a $t$ ve čtyřúhelníku $prqt$ větší než $180^o$ a tedy součet úhlů u vrcholů $p$ a $q$ v témže čtyřúhelníku je menší než $180^o$. (Součet všech úhlů ve čtyřúhelníku je $360^o$.)
Proto je hrana $rt$ v triangulaci $\mathcal T'$ legální.

Označme úhly před flipem a po něm podle následujícího obrázku:
\vskip 0.5cm

OBR 10.5 Označení úhlů str 4 
\vskip 0.5cm

Protože všechny další trojúhelníky mají obě triangulace stejné, stačí nám k tomu, aby
$$\alpha(\mathcal T)<\alpha(\mathcal T'),$$
dokázat že
$$\min \{\alpha_i,\ i=1,2,\dots,6\}<\min \{\beta_i,\ i=1,2,\dots,6\}.$$ 
Ukážeme postupně, že každé $\beta_i$ je větší než některé $\alpha_j$.
Zřejmě
$$\beta _1>\alpha_1\quad\text{ a }\quad \beta_4>\alpha_5.$$
Dále $\beta _2$ je obvodový úhel pro tětivu $pr$ v kružnici opsané
trojúhelníku $prt$, zatímco bod $q$ leží vně této kružnice, proto
$$\beta_2>\alpha_5.$$
Obdobně $\beta _6$ je obvodový úhel pro tětivu $pt$ v kružnici opsané
trojúhelníku $prt$,  proto
$$\beta_6>\alpha_4.$$
Analogicky, pomocí kružnice opsané trojúhelníku $qrt$ se přesvědčíme, že
$$\beta_3>\alpha_1\quad \text{ a }\quad \beta_5>\alpha_2.$$
\end{proof}

\begin{cor}\label{uol}
Úhlově optimální triangulace je legální. 
\end{cor}

\begin{proof} Kdyby úhlově optimální triangulace měla nějakou ilegální hranu, pak jejím flipem bychom dostali triangulaci, která v námi definovaném uspořádání je nad původní triangulací, což je spor s definicí úhlově optimální triangulace.
\end{proof}

Legální triangulace nemusí být úhlově optimální triangulace, jak ukazuje následující obrázek dvou triangulací pětiúhelníka $p_1p_2p_3p_4p_5$, kterému lze opsat kružnici.
Navíc $p_1p_2p_3p_5$ je čtverec a $p_5p_3p_4$ rovnoramenný trojúhelník. Obě triangulace $\mathcal T$ i $\mathcal T'$ jsou legální, ale protože  
$\alpha(\mathcal T)<\alpha(\mathcal T')$, není triangulace $\mathcal T$  úhlově optimální.
\vskip 0.5cm

OBR 10.6 Příklad legální triangulace, která není úhlově optimální.
\vskip 0.5cm


 


\subsection*{Delaunayův graf a triangulace} Kromě úhlově optimální a legální triangulace zavedeme ještě pojem Delaunayovy triangulace. Nejdřív ale definujme, co je Delaunayův graf.

{\it Delaunayův graf} je graf, který má jako uzly body množiny $P$. Dva uzly $p_i$, $p_j$ jsou spojeny hranou, právě když existuje kružnice, na které leží tyto dva body a všechny další body z množiny $P$ leží vně této kružnice. To znamená, že střed této kružnice leží na hraně diagramu Voronoia, která prochází mezi oblastí určenou bodem $p_i$ a oblastí určenou bodem $p_j$. Tedy Delaunayův graf je duální k diagramu Voronia. 
\vskip 0.5cm

OBR 10.7 Dualita diagramu Voronia (čárkovaný) a Delaunayova grafu (červený)
\vskip 0.5cm

\begin{lemma} Delaunayův graf je rovinným grafem. 
\end{lemma}

\begin{proof} Předpokládejme, že $p_ip_j$ a $p_kp_l$ jsou dvě hrany Delaunayova grafu, které se jako úsečky protínají ve vnitřním bodě. Nechť čtyřúhelník $p_ip_kp_jp_l$ má součet úhlů u vrcholů $p_k$ a $p_l$ aspoň $180^o$. Potom bod $p_l$ leží uvnitř každé kružnice, která má tětivu $p_ip_j$ a bod $p_k$ leží v jejím vnějšku. (Kdyby ležel vně, tak součet protilehlých úhlů u $p_k$ a $p_l$ by byl menší než $180^o$.) 
To je ale spor s tím, že $p_ip_j$ je hranou Delaunayova grafu.
\end{proof}
\vskip 0.5cm

OBR 10.8 Ilustrace k důkazu lemmatu 10.5
\vskip 0.5cm

Omezené oblasti Delaunayova grafu jsou tedy mnohoúhelníky. Nechť
body $p_1,p_2,\dots,$ $p_k$ tvoří vrcholy jednoho z těchto mnohoúhelníků. Tento mnohoúhelník určuje vrchol $v$ v duálním grafu, tedy v diagramu Voronoia.  Tedy body $p_1,p_2,\dots,p_k$ mají stejnou vzdálenost od vrcholu $v$ a proto leží na jediné kružnici se středem $v$.
\vskip 0.5cm

OBR 10.9 Čtyřúhelník $p_1p_2p_3p_4$ v Delaunayově grafu (černě) a diagram Voronoia
(červeně)
\vskip 0.5cm

{\it Delaunayova triangulace} je potom definována jako libovolná triangulace, která vznik\-ne rozdělením těchto mnohoúhelníků v Delaunayově grafu na trojúhelníky. Delaunayova triangulace tedy nemusí být určena jednoznačně. Nicméně platí, že středy kružnic opsaných trojúhelníkům v Delaunayově triangulaci vytvářejí množinu vrcholů diagramu Voronoia. 
\vskip 0.5cm

OBR 10.10 Delaunayův graf (černě) a Delaunayova triangulace (černě a červeně)
\vskip 0.5cm

Jestliže žádné čtyři body množiny $P$ neleží na kružnici, pak je Delaunayův graf již triangulací. V takovém případě je Delaunayova triangulace určena jednoznačně. Říkáme, že body množiny $P$ jsou v obecné poloze.

Každou Delaunayovu triangulaci lze charakterizovat následující vlastností.

\begin{lemma} Triangulace konvexního obalu množiny $P$ je Delaunayova, právě když pro každou její hranu $p_ip_j$ platí: kružnice opsaná přilehlému trojúhelníku $p_ip_jp_k$ neobsahuje uvnitř žádný další bod množiny $P$.
\end{lemma}

\begin{proof} K důkazu použijeme dualitu mezi Delaunayovým grafem a diagramem Voronoia.

Nechť je triangulace Delaunayova. Pak trojúhelník $p_ip_jp_k$ vznikl rozdělením nějakého mnohoúhelníka Delaunayova grafu na trojúhelníky.
Pak střed kružnice opsané troj\-ú\-hel\-ní\-ku $p_ip_jp_k$ je rovněž středem tohoto mnohoúhelníka a vrcholem diagramu Voronoia. Proto uvnitř této kružnice nemůže ležet žádný další bod množiny $P$.

Nechť obráceně uvnitř kružnice opsané trojúhelníku $p_ip_jp_k$ leží bod 
$p_l\in P$. Potom střed této kružnice není vrcholem diagramu Voronoia na hranici  oblastí bodů $p_i$, $p_j$ a $p_k$, neboť má k těmto bodům větší vzdálenost než k $p_l$. A tedy trojúhelník $p_ip_jp_k$ nemohl vzniknout triangulací mnohoúhelníkových oblastí Delaunayova grafu (duálního k diagramu Voronoia).
\end{proof}

Použijeme-li toto lemma a charakterizaci legální triangulace pomocí lemmatu
\ref{legal}, dostáváme okamžitě, že každá Delaunayova triangulace je legální. Trochu obtížnější je dokázat, že každá legální triangulace je Delaunayova.

\begin{thm} Množina legálních triangulací se rovná množině Delaunayových triangulací. 
\end{thm} 

\begin{proof} Dokažme sporem, že každá legální triangulace je Delaunayova. Nechť $\mathcal T$ je legální triangulace, která není Delauneyova. V této triangulaci tedy existuje trojúhelník $p_ip_jp_k$ a bod $p_l$ tak, že $p_l$ leží uvnitř kružnice opsané trojúhelníku $p_ip_jp_k$ a úhel $\angle p_ip_lp_j$ je maximální pro všechny takové trojúhelníky a body. Nechť $p_ip_jp_m$ je trojúhelník přilehlý k trojúhelníku $p_ip_jp_k$ v triangulaci $\mathcal T$. Protože je tato triangulace legální, neleží bod $p_m$ uvnitř kružnice opsané trojúhelníku
$p_ip_jp_k$. Bod $p_l$ nemůže ležet uvnitř trojúhelníku $p_ip_jp_m$. Nechť $p_l$ leží na opačné straně přímky $p_jp_m$ než bod $p_i$. Potom je z následujícího obrázku 
vidět, že pro veliklosti úhlů platí:
$$\angle p_mp_lp_j>\angle p_ip_lp_j,$$
což je ve sporu s volbou trojúhelníka $p_ip_jp_k$ a bodu $p_l$.
\end{proof}
\vskip 0.5cm

OBR 10.11 K důkazu věty 10.7
\vskip 0.5cm


Odtud a z důsledku \ref{uol} plyne:
\begin{cor} 
\begin{enumerate}
\item Každá úhlově optimální triangulace je Delaunayova.
\item Jsou-li body množiny $P$ v obecné poloze, tj. žádné čtyři neleží na jedné kružnici, pak existuje právě jedna Delaunayova triangulace, právě jedna legální triangulace a právě jedna úhlově optimální triangulace a tyto triangulace jsou totožné.
\end{enumerate}
\end{cor}





\subsection*{Základní idea náhodnostního přírůstkového algoritmu} Jedna možnost algoritmicky konstruovat Delaunayovu triangulaci je využít algoritmus k nalezení diagramu Voronoia, k němu najít duální graf a jeho $k$-úhelníky rozdělit na trojúhelníky.

My si zde ukážeme jiný přístup, který je založen na tom, že každá legální triangulace je Delaunayova, a který spočívá v postupném odstraňování nelegálních hran.

Naivní verze takového algoritmu je následující: Vytvoříme nějakou triangulaci a v ní procházíme její hrany. Když nalezneme ilegální hranu, vyměníme ji flipem za hranu legální a stejným postupem pokračujeme dál. Tento proces je konečný, neboť po každém flipu dostaneme triangulaci, která je v popsaném lexikografickém uspořádání větší než ta předchozí. Vzhledem k tomu, že triangulací je konečný počet, musí tento proces někdy skončit. 

Sofistikovanou verzí tohoto přístupu je náhodnostní přírůstkový algoritmus. Základní idea 
tohoto algoritmu je následující:
\begin{enumerate}
\item K bodům množiny $P$ přidáme body $\pj$ a $\pd$ tak, aby s bodem $p_0\in P$, který má v $P$ maximální $y$-ovou souřadnici (případně maximální $x$-ovou souřadnici), tvořily trojúhelník, v němž leží všechny ostatní body množiny $P$.
\item Tyto body uspořádáme náhodně do posloupnosti $p_1,p_2,\dots,p_n$. Body $p_r$ pro
$r=1,2,\dots,n$ postupně přidáváme k legální triangulaci $\mathcal T_{r-1}$ trojúhelníka $p_0\pj\pd$, kde vrcholy jednotlivých trojúhelníků jsou
$$\pd,\pj,p_0,p_1,\dots,p_{r-1}.$$
\item  Pomocí současně konstruované vyhledávací struktury zjistíme do vnitřku 
kte\-ré\-ho trojúhelníku $p_ip_jp_k$ nebo do které hrany $p_ip_j$ triangulace $\mathcal T_{r-1}$ bod $p_r$ padne. Potom hranami spojíme bod $p_r$ s vrcholy tohoto trojúhelníku nebo s vrcholy přilehlých trojúhelníků, padne-li na hranu. Nově vzniklou triangulaci trojúhelníku $p_0\pj\pd$ s vrcholy trojúhelníků v množině 
$$\{\pd,\pj,p_0,p_1,\dots,p_{r-1},p_r\}$$
"legalizujeme", tj. pomocí flipů měníme ilegální hrany za legální. Po odstranění všech
ilegálních hran dostaneme triangulaci $\mathcal T_r$.
\item Na závěr z legální triangulace $\mathcal T_n$ množiny $P\cup\{\pj,\pd\}$ odstraníme body $\pj$ a $\pd$ a hrany z nich vycházející. Díky vhodné volbě těchto dvou bodů, bude zbylá triangulace legální, tedy i Delaunayovou triangulací konvexního obalu množiny $P=\{p_0,p_1,p_2,\dots,p_n\}$.
\end{enumerate}
\vskip 0.5cm

OBR 10.12 Množina $P$ v trojúhelníku $p_0\pj\pd$.
\vskip 0.5cm  

Nyní jednotlivé kroky popíšeme podrobněji. Začneme krokem (2) a (3).

\subsection*{Legalizace} Uvažujme legální triangulaci $\mathcal T_{r-1}$ popsanou 
v bodě (2). Jestliže pomocí vyhledávací struktury zjistíme, že bod $p_r$ leží uvnitř trojúhelníka $p_ip_jp_k$, spojíme jej hranami s jednotlivými vrcholy.
\vskip 0.5cm

OBR 10.13 Bod $p_r$ v trojúhelníku $p_ip_jp_k$.
\vskip 0.5cm 

Tím vznikne nová triangulace. Podstatné je, že nově přidané hrany vycházející z~bodu
$p_r$ jsou legální. To dokážeme takto: Nechť $\mathcal K$ je kružnice opsaná trojúhelníku $p_ip_jp_k$.
Protože je triangulace $\mathcal T_{r-1}$ legální a tedy i Delaunayova, neleží uvnitř kružnice $\mathcal K$ žádný z bodů z množiny $P_{r-1}=\{\pd,\pj, p_0,\dots,p_{r-1}\}$. Nechť $\mathcal L$ je kružnice stejnolehlá s $\mathcal K$, která má tětivu $p_rp_i$. Viz obrázek. Uvnitř této kružnice neleží rovněž žádné další body $P_{r-1}$. Tedy hrana $p_rp_i$ je hranou Delaunayova grafu pro množinu $P_r$ a ta musí být legální. Analogicky se dokáže, že i hrany $p_rp_j$ a $p_rp_k$ jsou legální.
\vskip 0.5cm

OBR 10.14 K důkazu, že $p_rp_i$ je legální.
\vskip 0.5cm

Může se ale stát, že některá z hran $p_ip_j$, $p_ip_k$ a $p_jp_k$ se v nové triangulaci stane ilegální hranou. Pak je potřeba ji pomocí flipu nahradit hranou vycházející z bodu $p_r$. Nechť například $p_ip_j$ je ilegální. Pak je to hrana nejen trojúhelníku $p_ip_jp_r$ ale také dalšího trojúhelníku $p_ip_jp_l$. Nahradíme ji tedy hranou $p_rp_l$, která je již legální.  Teď se ale může stát ilegální některá z hran $p_ip_l$ a $p_jp_l$. Proto ji opět pomocí flipu nahradíme hranou vycházející z bodu $p_r$. 
\vskip 0.5cm

OBR 10.15 Hrana $p_ip_j$ je ilegální.
\vskip 0.5cm

V tomto postupu pokračujeme tak dlouho, až v triangulaci nebude žádná ilegální hrana. (Po každém flipu je nová triangulace v daném lexikografickém uspořádání větší než ta předchozí.)
Postup zachycuje následující animace a pseudokód. Vstupem psedokódu je bod $p_r$, hrana $p_ip_j$ a legální triangulace $\mathcal T_{r-1}$.
\vskip 0.5cm

ANIMACE
\vskip 0.5cm

PSEUDOKÓD 37 z pseudo.pdf  Prosím nepsat pruh nad úsečkami, místo $\mathcal T$ použít $\mathcal T_{r-1}$ a místo $p_k$ psát $p_l$.
\vskip 0.5cm  

Jestliže pomocí vyhledávací struktury zjistíme, že bod $p_r$ leží na hraně $p_ip_j$, pak hranu
$p_ip_j$ nahradíme hranami $p_rp_i$ a $p_rp_j$ a vytvoříme další hrany spojením bodu $p_r$ s vrcholy $p_k$ a $p_l$ přilehlých trojúhelníků ke hraně $p_ip_j$. Stejně jako v předchozím se dokáže, že nové hrany $p_rp_i$, $p_rp_j$, $p_rp_k$ a $p_rp_l$ jsou legální.
Nelegálními se ale mohou stát hrany $p_ip_k$, $p_jp_k$, $p_ip_l$ a $p_jp_l$. To opravíme postupným prováděním flipů stejně jako v předchozím případě.
\vskip 0.5cm

OBR 10.16 Bod $p_r$ na hraně $p_ip_j$.
\vskip 0.5cm  

\subsection*{Vyhledávací struktura} 
V průběhu algoritmu máme ke každé triangulaci příslušnou vyhledávací strukturu. Je to orientovaný graf, jehož listy jsou trojúhelníky aktuální triangulace a vnitřními uzly jsou trojúhelníky předchozích triangulací.

Na začátku má triangulace $\mathcal T_0$ jediný trojúhelník $p_0\pj\pd$ a vyhledávací struktura $\mathcal D_0$ jediný uzel, který je listem a odpovídá tomuto trojúhelníku.
Pro triangulaci $\mathcal T_{r-1}$ máme vyhledávací strukturu $\mathcal D_{r-1}$. Nyní triangulaci $\mathcal T_{r-1}$ postupně měníme způsobem popsaným v předchozí části.
Každému přechodu od jedné triangulace k další triangulaci odpovídá jednoznačně určený přechod od jedné vyhledávací struktury k další vyhledávací struktuře. Ukažme si to na obrázku:
\vskip 0.5cm

OBR 10.17 Změna vyhledávací struktury při vytvoření hran uvnitř trojúhelníku.
\vskip 0.5cm
 
OBR 10.18 Změna vyhledávací struktury při flipu.
\vskip 0.5cm

Tímto postupem tedy současně s postupným vytvořením triangulace $\mathcal T_r$ vytvoříme postupně i vyhledávací strukturu $\mathcal D_r$. Ta závisí pouze na pořadí bodů $p_1,p_2,\dots,p_r$.  

\subsection*{Počáteční volba bodů $p_0$, $p_{-1}$, $p_{-2}$}
Nyní si blíže objasníme kroky (1) a (4) našeho algoritmu. Budeme se přitom pro lepší pochopení odvolávat na geometrickou představu. Body $\pj$ a $\pd$ budou určeny svými vlastnostmi, žádné jejich konkrétní souřadnice určovat nebudeme. Rovněž o tom, zda je nějaká hrana legální či ilegální, a mezi čtyřmi body, které vstupují do hry, bude některý z bodů $\pj$, $\pd$, nebude rozhodovat výpočet, ale pouze pravidla, které vyplývají z vlastností bodů $\pj$ a $\pd$.

Jak jsme již řekli, za bod $p_0$ zvolíme ten z bodů množiny $P$, který je maximální v lexikografickém uspořádání prvně podle souřadnice $y$ a pak podle souřadnice $x$. 

Bod $\pj$ zvolíme vpravo dole od množiny $P$. (Exaktněji řečeno, jeho $y$-ová souřadnice je menší než minimum $y$-ových souřadnic bodů množiny $P$ a jeho 
$x$-ová souřadnice je větší než maximum $x$-ových souřadnic bodů množiny $P$.)
Přitom volbu $\pj$ provedeme tak, 
\begin{itemize}
\item aby ležel vně všech kružnic určených každou trojicí 
bodů z množiny $P$, které neleží na přímce,
\item aby všechny body množiny $P$ ležely pod přímkou $p_0\pj$.
\end{itemize}

Bod $\pd$ zvolíme vlevo nahoře od množiny $P$ tak,
\begin{itemize}
\item aby ležel vně všech kružnic určených každou trojicí 
bodů z množiny $P\cup\{\pj\}$, které neleží na přímce,
\item aby všechny body množiny $P$ ležely pod přímkou $p_0\pd$,
\item aby všechny body množiny $P$ ležely nad přímkou $\pj\pd$.
\end{itemize}
Tedy všechny body množiny $P$ leží uvnitř trojúhelníka $p_0\pj\pd$, každý čtyřúhelník
$\pd p_i \pj p_j$ je nekonvexní a v důsledku toho bod $\pd$ leží vně všech kružnic opsaných trojúhelníkům $\pd p_i p_j$.
\vskip 0.5cm

OBR 10.19 Množina $P$ v trojúhelníku $p_0\pj\pd$.
\vskip 0.5cm

Za těchto předpokladů je každá Delaunayova (legální) triangulace složena
\begin{enumerate}
\item ze spojnic bodu $\pj$ s vrcholy pravé části hranice konvexního obalu množiny $P$,
\item ze spojnic bodu $\pd$ s vrcholy levé části hranice konvexního obalu množiny $P$,
\item z Delaunayovy triangulace množiny $P$. 
\end{enumerate}
Díky tomu, získáme Delaunayovu triangulaci množiny $P$ tak, jak je popsáno v kroku (4).

 Pravidla pro práci s algoritmem vycházejí z  lemmatu:

\begin{lemma} \label{ekv} Při výše popsané volbě bodů $p_0$, $\pj$ a $\pd$ jsou následující tvrzení ekvivalentní:
\begin{itemize}
\item $p_j$ leží vlevo od orientované přímky $p_i\pj$. 
\item $p_j$ leží vlevo od orientované přímky $\pd p_i$.
\item $p_j>p_i$ v lexikografickém uspořádání njedřív podle $y$, pak podle $x$.
\end{itemize}
\end{lemma}
Místo provádění důkazu demonstrujme situaci obrázkem.
\vskip 0.5cm

OBR 10.20 K lemmatu \ref{ekv}. Body $\pj$ a $\pd$ jsou vybrány tak, že v barevně vyznačených úhlech neleží žádný další bod množiny $P$.
\vskip 0.5cm

Při zjišťování, zda je hrana legální či ilegální postupujeme takto:
\begin{itemize}
\item Všechny hrany trojúhelníka $p_0\pj\pd$ jsou legální.
\item Hrana $\pd p_j$ s přilehlými vrcholy $\pj$ a $p_k$ je legální.
\end{itemize}
\vskip 0.5cm
OBR 10.21 Ilustrace předchozího tvrzení.
\vskip 0.5cm

\begin{itemize}
\item Hrana $\pj p_j$  s přilehlými vrcholy $\pd$ a $p_k$ je legální.
\item Nechť hrana $p_i p_j$ má přilehlé vrcholy $p_k$ a $p_l$, čtyřúhelník
$p_ip_kp_jp_l$ je konvexní a mezi čísly $i,j,k,l$ je právě jedno záporné. Pak je hrana $p_ip_j$ legální, právě když
$$\min(k.l)<\min(i,j).$$  
\end{itemize}
\vskip 0.5cm
OBR 10.22 $\min(-2,l)<\min(i,j)$, hrana $p_ip_j$ je legální.
\vskip 0.5cm

OBR 10.23 $\min(k,l)>\min(-1,j)$, hrana $\pj p_j$ je ilegální.

\subsection*{Pseudokód algoritmu a jeho očekávaná časová náročnost}
Stručný pseudokód algoritmu popsaného detailněji v předchozích částech můžeme podat takto:
\vskip 0.5cm

PSEODOKÓD číslo 36 z pseudo.pdf
\vskip 0.5cm

Bez důkazu, který lze najít v [Berg et al], uvedeme větu o očekávané časové náročnosti tohoto náhodnostního algoritmu.

\begin{thm} Očekávaná časová náročnost náhodnostního přírůstkového algoritmu pro Delaunayovu triangulaci množiny o $n+1$ prvcích je $O(n\log n)$. 
\end{thm}
\end{document} 

