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$
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))$.
Obrázek 10.1 Lineární aproximace funkce $f$
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.
Ú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úhelníků. To nám dá možnost porovnávat různé triangulace lexikograficky podle velikosti úhlů.
Věta 10.1
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.
Důkaz
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.$$
\(\Box\)
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
Triangulace $\mathcal T$ se nazývá úhlově optimální, jestliže je maximální v tomto uspořádání.
Legální hrany a legální triangulace
Pro účely našeho algoritmu na vytváření vhodné triangulace budeme potřebovat pojem legální hrany a 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 obvodovými úhly tětivy $pq$ pro jednotlivé oblouky kružnice $\mathcal K$. Obvodové úhly mají tyto dvě důležité vlastnosti:
Velikost úhlů $\alpha$ a $\beta$ nezávisí na poloze bodů $a$ a $b$ v daných obloucích.
Součet $\alpha+\beta=180^o$.
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\gt\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\lt\alpha.$$
Obrázek 10.2 Obvodové úhly
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 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$.
Obrázek 10.3 Ilegální hrana $pq$
Hrany triangulace $\mathcal T$, které nejsou ilegální nazýváme legální
a triangulaci bez ilegálních hran nazýváme legální triangulací.
Bezprostředním důsledkem této definice je následující charakterizace legální triangulace:
Lemma 10.2
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$.
Zásadní význam pro náš algoritmus má následující tvrzení.
Lemma 10.3
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)\lt\alpha(\mathcal T').$$
Výše uvedená výměna hrany $pq$ za $rt$ se nazývá flipem.
Obrázek 10.4 Flip
Důkaz
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:
Obrázek 10.5 Označení úhlů str 4
Protože všechny další trojúhelníky mají obě triangulace stejné, stačí nám k tomu, aby
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.
\(\Box\)
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)\lt\alpha(\mathcal T')$, není triangulace $\mathcal T$ úhlově optimální.
Obrázek 10.6 Příklad legální triangulace, která není úhlově optimální.
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.
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.
Obrázek 10.7 Dualita diagramu Voronia (čárkovaný) a Delaunayova grafu (červený)
Lemma 10.5
Delaunayův graf je rovinným grafem.
Důkaz
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.
\(\Box\)
Obrázek 10.8 Ilustrace k důkazu lemmatu 10.5
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$.
Obrázek 10.9 Čtyřúhelník $p_1p_2p_3p_4$ v Delaunayově grafu (černě) a diagram Voronoia (červeně)
Delaunayova triangulace je potom definována jako libovolná triangulace, která vznikne 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.
Obrázek 10.10 Delaunayův graf (černě) a Delaunayova triangulace (černě a červeně)
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í.
Lemma 10.6
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$.
Důkaz
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úhelní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).
\(\Box\)
Použijeme-li toto lemma a charakterizaci legální triangulace pomocí lemmatu, 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.
Věta 10.7
Množina legálních triangulací se rovná množině Delaunayových triangulací.
Důkaz
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\gt\angle p_ip_lp_j,$$
což je ve sporu s volbou trojúhelníka $p_ip_jp_k$ a bodu $p_l$.
\(\Box\)
Obrázek 10.11 K důkazu věty 10.7
Odtud a z důsledku plyne:
Důsledek 10.8
Každá úhlově optimální triangulace je Delaunayova.
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é.
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í:
K bodům množiny $P$ přidáme body $p_{-1}$ a $p_{-2}$ 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$.
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_0p_{-1}p_{-2}$, kde vrcholy jednotlivých trojúhelníků jsou
$$p_{-2},p_{-1},p_0,p_1,\dots,p_{r-1}.$$
Pomocí současně konstruované vyhledávací struktury zjistíme do vnitřku
které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_0p_{-1}p_{-2}$ s vrcholy trojúhelníků v množině
$$\{p_{-2},p_{-1},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$.
Na závěr z legální triangulace $\mathcal T_n$ množiny $P\cup\{p_{-1},p_{-2}\}$ odstraníme body $p_{-1}$ a $p_{-2}$ 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\}$.
Obrázek 10.12 Množina $P$ v trojúhelníku $p_0p_{-1}p_{-2}$.
Nyní jednotlivé kroky popíšeme podrobněji. Začneme krokem (2) a (3).
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.
Obrázek 10.13 Bod $p_r$ v trojúhelníku $p_ip_jp_k$.
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}=\{p_{-2},p_{-1}, 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í.
Obrázek 10.14 K důkazu, že $p_rp_i$ je legální.
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$.
Obrázek 10.15 Hrana $p_ip_j$ je ilegální.
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}$.
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ě.
Obrázek 10.16 Bod $p_r$ na hraně $p_ip_j$.
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_0p_{-1}p_{-2}$ 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:
Obrázek 10.17 Změna vyhledávací struktury při vytvoření hran uvnitř trojúhelníku.
Obrázek 10.18 Změna vyhledávací struktury při flipu.
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$.
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 počítat nebudeme. Při rozhodování, zda je nějaká hrana legální či ilegální, uvažujeme čtyři body. Není-li mezi nimi žádný z bodů $\pj$, $\pd$, musíme najít střed kružnice opsané třem z těchto bodů a zjistit, zda čtvrtý bod leží v jejím vnitřku. V případě, že mezi těmito body je některý z bodů $\pj$ nebo $\pd$ budeme při rozhodování postupovat podle pravidel uvedených níže. Tato pravidla vyplývají z toho, jakým způsobem body $\pj$ a $\pd$ volíme.
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 $p_{-1}$ 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 $p_{-1}$ provedeme tak,
aby ležel vně všech kružnic určených každou trojicí
bodů z množiny $P$, které neleží na přímce,
aby všechny body množiny $P$ ležely pod přímkou $p_0p_{-1}$.
Bod $p_{-2}$ zvolíme vlevo nahoře od množiny $P$ tak,
aby ležel vně všech kružnic určených každou trojicí
bodů z množiny $P\cup\{p_{-1}\}$, které neleží na přímce,
aby všechny body množiny $P$ ležely pod přímkou $p_0p_{-2}$,
aby všechny body množiny $P$ ležely nad přímkou $p_{-1}p_{-2}$.
Tedy všechny body množiny $P$ leží uvnitř trojúhelníka $p_0p_{-1}p_{-2}$, každý čtyřúhelník
$p_{-2} p_i p_{-1} p_j$ je nekonvexní a v důsledku toho bod $p_{-2}$ leží vně všech kružnic opsaných trojúhelníkům $p_{-2} p_i p_j$.
Obrázek 10.19 Množina $P$ v trojúhelníku $p_0p_{-1}p_{-2}$.
Za těchto předpokladů je každá Delaunayova (legální) triangulace složena
ze spojnic bodu $p_{-1}$ s vrcholy pravé části hranice konvexního obalu množiny $P$,
ze spojnic bodu $p_{-2}$ s vrcholy levé části hranice konvexního obalu množiny $P$,
z Delaunayovy triangulace množiny $P$.
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:
Lemma 10.9
Při výše popsané volbě bodů $p_0$, $p_{-1}$ a $p_{-2}$ jsou následující tvrzení ekvivalentní:
$p_j$ leží vlevo od orientované přímky $p_ip_{-1}$.
$p_j$ leží vlevo od orientované přímky $p_{-2} p_i$.
$p_j\gt p_i$ v lexikografickém uspořádání njedřív podle $y$, pak podle $x$.
Místo provádění důkazu demonstrujme situaci obrázkem.
Obrázek 10.20 K lemmatu 10.9. Body $p_{-1}$ a $p_{-2}$ jsou vybrány tak, že v barevně vyznačených úhlech neleží žádný další bod množiny $P$.
Při zjišťování, zda je hrana legální či ilegální postupujeme takto:
Všechny hrany trojúhelníka $p_0p_{-1}p_{-2}$ jsou legální.
Hrana $p_{-2} p_j$ s přilehlými vrcholy $p_{-1}$ a $p_k$ je legální.
Obrázek 10.21 Ilustrace předchozího tvrzení.
Hrana $p_{-1} p_j$ s přilehlými vrcholy $p_{-2}$ a $p_k$ je legální.
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)\lt\min(i,j).$$
Obrázek 10.22 $\min(-2,l)\lt\min(i,j)$, hrana $p_ip_j$ je legální.
Obrázek 10.23 $\min(k,l)\gt\min(-1,j)$, hrana $p_{-1} p_j$ je ilegální.
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:
AlgorithmDelaunayTriangulation(P)
Input. A set $P$ of $n+1$ points in the plane.
Output. A Delaunay triangulation of $P$.
Let $p_0$ be the lexicographically highest point of $P$, that is, the rightmost among the points with largest $y$-coordinate.
Let $p_{-1}$ and $p_{-2}$ be two points in $\mathcal R^2$ sufficiently far away and such that $P$ is contained in the triangle $p_0p_{-1}p_{-2}$.
Initialize $\mathcal T$ as the triangulation consisting of the single triangle $p_0p_{-1}p_{-2}$.
Compute a random permutation $p_1, p_2,\ldots, p_n$ of $P \setminus \{p_0\}$.
for $r\leftarrow 1$ to $n$
do (* Insert $p_r$ into $\mathcal T$: *)
Find a triangle $p_ip_jp_k\in \mathcal T$ containing $p_r$.
if $p_r$ lies in the interior of the triangle $p_ip_jp_k$
then Add edges from $p_r$ to the three vertices of $p_ip_jp_k$, thereby splitting $p_ip_jp_k$ into three triangles.
else (* $p_r$ lies on an edge of $p_ip_jp_k$, say the edge $\overline{p_ip_j}$ *)
Add edges from $p_r$ to $p_k$ and to the third vertex $p_l$ of the other triangle that is incident to $\overline{p_ip_j}$, thereby splitting the two triangles incident to $\overline{p_ip_j}$ into four triangles.
