% 9. Diagramy Voronoia
\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\R{\mathbb{R}}
\def\d{\operatorname{dist}}

\begin{document}

\setcounter{section}{8}
\section{\large Diagramy Voronoia}

\subsection*{Úvod.}
Diagramy Voronoia podávají řešení problému známého pod anglickým názvem "post office problem".
V něm jde o to rozdělit teritorium města na oblasti okolo jednotlivých pošt tak, aby v každé oblasti byla místní pošta ta nejbližší. Jiným příkladem je určení spádových oblastí nemocnic podle vzdálenosti. Matematická formulace problému je následující:

V rovině je dána množina bodů $P=\{p_1,p_2,\dots,p_n\}$. {\it Diagram Voronoia} (zkráceně V-diagram) je rovinné podrozdělení, které má oblasti
$$V(p_i)=\{q\in \R^2;\ \d(q,p_i)\leq \d(q,p_j) \text{ pro všechna }j\in P\setminus\{i\} \},$$
kde $\d(q,p)$ označuje klasickou vzdálenost bodů $q$ a $p$.
\medskip

OBR 9.1  Příklad diagramu Voronoia. 
\medskip

Množinou bodů v rovině, které mají vzdálenost k bodu $p_i$ menší nebo rovnu vzdá\-le\-nosti k bodu
$p_j\ne p_i$ je polorovina
$$h(p_i,p_j)=\{q\in \R^2;\ \d(q,p_i)\leq \d(	q,p_j)\}.$$
Oblast Voronia $V(p_i)$ je tedy rovna průniku všech takových polorovin pro $j\ne i$
$$h(p_i,p_j)=\bigcap_{j\in P\setminus\{i\}}h(p_i,p_j).$$
Průnik $n-1$ polorovin umíme podle 5. kapitoly najít v čase $O(n\log n)$ nebo podle 6. kapitoly
v očekávaném čase $O(n)$. Najít tímto způsobem všechny oblasti by vyžadovalo čas aspoň
$O(n^2)$. My si ukážeme algoritmus pro nalezení diagramu Voronoia s časovou náročností $O(n\log n)$. O tom, že taková časová náročnost je reálná, svědčí následující tvrzení:

\begin{thm} Diagram Voronoia pro $n\geq 3$ bodů má nejvýše $2n-5$ vrcholů a nejvýše $3n-6$ hran.
\end{thm}

\begin{proof} Označme $m$ počet vrcholů a $h$ počet hran V-diagramu. Přidáním vrcholu $v_{\infty}$ v "nekonečnu", do kterého vedou všechny hrany
V-diagramu, které jsou polopřímky, vytvoříme z V-digramu rovinný graf, který má $n$ oblastí, $m+1$ uzlů a $h$ hran. Viz obrázek. 
\medskip

OBR 9.2 Doplnění V-digramu na planární graf.
\medskip
 
Pro něj platí Eulerova věta
$$m+1-h+n=2.$$
Stupeň každého uzlu je aspoň 3, součet všech stupňů je $2h$. Tedy
$$2h\geq 3(m+1).$$
Dosadíme-li do této nerovnosti  $h=m+n-1$ z Eulerovy věty, dostaneme
$$2m+2n-2\geq 3(m+1),$$
tedy po úpravě $m\leq 2n-5$. Obdobně po dosazení $m=h-n+1$ je
$$2h\geq 3(h-n+2),$$
což dává $h\leq 3n-6$.
\end{proof}

Pro množinu $P$ a každý bod $q\in \R^2\setminus P$ definujeme kruh se středem $q$ a poloměrem, který je roven vzdálenosti bodu $q$ od množiny $P$ 
$$C_P(q)=\{r\in \R^2;\ \d(q,r)\leq \d(q,P)\}.$$
Na kružnici ohraničující tento kruh leží vždy aspoň jeden bod množiny $P$.  

Je zřejmé, že platí následující tvrzení:

\begin{lemma} Bod $q$ leží na hraně V-diagramu, právě když na hranici $C_P(q)$ leží aspoň dva body z množiny $P$. 

Bod $r$ je vrcholem V-diagramu, právě když na hranici $C_P(r)$ leží aspoň tři body z množiny $P$.
\end{lemma}
\medskip

OBR 9.3 Ilustrace lemmatu 9.2.
\medskip

 
\subsection{Metoda zametací přímky}
Jeden z možných algoritmů pro konstrukci V-dia\-gra\-mu používá metodu zametací přímky, ale v podobě, která je poněkud sofistikovanější než byly ty, se kterými jsme se prozatím setkali.
Zametací přímka $l$ postupuje rovinou shora dolů a nad ní se vytváří V-diagram. Tento diagram nemůže vznikat v celé polorovině $l^+$ nad přímkou $l$, ale pouze v její části, která je sjednocením oblastí nad jistými parabolami. Jak taková oblast vypadá?

Bod $q$ leží v této oblasti, jestliže pro některý bod $p_i\in P\cap l^+$ platí
$$\d(q,p_i)\leq \d(q,l).$$
Pak totiž pro všechny body $p_j\in P$ z  poloroviny $l^-$ pod přímkou $l$ je
$$\d(q,p_i)\leq\d(q,l)\leq\d(q,p_j).$$
Tedy bod $q$ z této oblasti určitě neleží v oblasti Voronoia $V(p_j)$ pro $p_j\in P\cap l^-$.

Označme $\alpha(p,l)$ parabolu tvořenou body, které mají stejnou vzdálenost od bodu $p$ i přímky $l$. Bod $p$ je ohniskem a přímka $l$ řídící přímkou této paraboly. Nechť $\alpha^+(p,l)$ je množina bodů ležících nad parabolou $\alpha(p,l)$ nebo na ní.
Oblast nad zametací přímkou $l$, kde bude V-diagram vytvořen, je sjednocení
$$\bigcup_{p_i\in P\cap l^+}\alpha^+(p_i,l).$$
Hranici této oblasti, tvořenou oblouky parabol, budeme nazývat {\it plážová linie} (beach line).

Strom $\mathcal T$ bude v tomto případě vyvážený binární strom, který ve svých listech udržuje pořadí oblouků parabol v plážové linii. Zlomové body plážové linie, tj. body kde se setkávají dva po sobě jdoucí oblouky plážové linie příslušné parabolám s ohnisky $p_1$ a $p_2$, mají stejnou vzdálenost od $p_1$ i $p_2$, neboť
$$\d(q,p_1)=\d(q,l)=\d(q,p_2),$$
a leží tedy na hranách diagramu Voronoia. Tyto zlomové body jsou vnitřními uzly stromu $\mathcal T$. Jejich popis tvaru $\langle p_1\,:\,p_2\rangle$ značí, že se jedná o průsečík parabol s ohnisky $p_1$ a $p_2$ (obě mají řídící přímku $l$) a to ten (obvykle jsou dva), který má oblouk paraboly s ohniskem $p_1$ zleva a oblouk paraboly s ohniskem $p_2$ zprava. Pomocí takového stromu lze pro bod $p$ na zametací přímce $l$ vyhledat oblouk plážové linie, který leží nad bodem $p$. Následující obrázek ukazuje příklad plážové linie a příslušného stromu.
\medskip

OBR 9.4 Plážová linie 
\medskip

OBR 9.5 Vyvážený binární strom příslušný předchozí plážové linii.

\subsection{Události}
Zásadní význam mají odpovědi na následující dvě otázky:
\begin{itemize}
\item Kdy se v plážové linii objeví nový oblouk?
\item Kdy z plážové linie nějaký oblouk zmizí?
\end{itemize}
Na tyto otázky odpovídají následující dvě lemmata. Jejich důkazy jsou technické, proto je nebudeme  provádět a raději se omezíme na jejich ilustraci pomocí obrázků.

\begin{lemma}
Nové oblouky v plážové linii vznikají, právě když zametací přímka prochází některým bodem množiny $P$. 
\end{lemma}
Takový bod nazýváme {\it místní událost}, anglicky site event. Situaci ilustruje následující obrázek. Zametací přímka $l$ prochází bodem $p\in P$. Nechť $\alpha$ je oblouk plážové linie nad bodem $p$, který je částí paraboly s ohniskem v bodě $p_1\in P$. Po průchodu zametací přímky bodem  $p$ se oblouk $\alpha$ rozdělí na dva oblouky $\alpha_1$ a $\alpha_2$ a mezi nimi vznikne v plážové linii nový oblouk $\beta$, který je částí paraboly s ohniskem v bodě $p$.
\medskip

OBR 9.6 Místní událost $p$
\medskip

V průniku dvojice oblouků $\alpha_1$ a $\beta$ a dvojice $\beta$ a $\alpha_2$ leží body hrany
diagramu Voronoia, která odděluje oblast $V(p_1)$ od oblasti $V(p)$. Této změně v plážové linii odpovídá následující změna ve stromě $\mathcal T$: 
\medskip

OBR 9.7 Změna ve stromě $\mathcal T $ 
\medskip

Vnitřní uzly $\langle p_1\, :\, p_2\rangle$,   $\langle p_1\,:\,p\rangle$ a  $\langle p\,:\,p_1\rangle$ stromu  $\mathcal T$ popisují zlomové body plážové linie  pomocí ohnisek příslušných parabol v pořadí zleva doprava tak, jak jsme to popsali výše. Po změně ve stromu $\mathcal T$ je potřeba provést jeho vyvážení.

Nyní uvažujme tři po sobě jdoucí oblouky $\alpha$, $\beta$ a $\gamma$ plážové linie. Nechť
$p_1$, $p_2$ a $p_3$ jsou postupně ohniska jim příslušejících parabol. Uvažujme kružnici opsanou těmto třem bodům.  Nazvěme $s$ její střed a označme $q$ nejspodnější bod této kružnice, tj. bod s minimální souřadnicí $y$. Jestliže bod $q$ leží pod zametací přímkou $l$, nazýváme jej {\it kruhovou událostí} pro oblouk $\beta$ (anglicky circle event).

Při průchodu přímky $l$ tímto bodem má střed $s$ kružnice opsané bodům $p_1$, $p_2$, $p_3$
a $q$ od těchto bodů stejnou vzdálenost jako od přímky $l$, leží tedy na všech třech obloucích
$\alpha$, $\beta$ a $\gamma$ plážové linie. Při posunu zametací přímky $l$ pod bod $q$, oblouk
$\beta$ mizí z plážové linie. Střed $s$ kružnice opsané je vrcholem diagramu Voronoia, do kterého přicházejí hrany oddělující oblast $V(p_1)$ od $V(p_2)$, oblast $V(p_2)$ od $V(p_3)$ 
a oblast $V(p_1)$ od $V(p_3)$.  
\medskip

OBR 9.8 Průchod zametací přímky  kruhovou událostí $q$
\medskip

OBR 9.9 Změna ve stromě $\mathcal T $  při průchodu kruhovou událostí
\medskip

\begin{lemma}
Oblouk paraboly mizí z plážové linie, právě když zametací přímka prochází přes jeho kruhovou událost.
\end{lemma}

\subsection{Algoritmus} Začátek algoritmu odpovídá poloze zametací přímky $l$ nad všemi body.  
Strom $\mathcal T$ je prázdný a fronta událostí $\mathcal Q$ obsahuje všechny body z množiny
$P$ (místní události) uspořádané lexikograficky shora dolů a zleva doprava. Při průchodu zametací přímky událostí provádíme v závislosti na tom, zda se jedná o místní nebo kruhovou událost, následující akce:
\begin{itemize}
\item přidáme oblouk do stromu $\mathcal T$ a hrany do dvojitě souvislého seznamu 
pro V-diagram,
\item vezmeme oblouk ze stromu $\mathcal T$, přidáme hranu a vrchol do V-diagramu,
\item  z fronty $\mathcal Q$ odebereme událost, kterou jsme právě prošli, případně kruhové události, které odpovídaly trojicím po sobě jdoucích oblouků, které po průchodu danou událostí
zmizely. Mění se totiž pořadí oblouků a aktuální kruhové události se počítají ze tří aktuálních po sobě jdoucích oblouků. Nově vzniklé kruhové události zařadíme do fronty.
\end{itemize}  
Tento postup provádíme tak dlouho, až je fronta $\mathcal Q$ prázdná. Strom $\mathcal T$ však prázdný nebude. Jeho aktuální vnitřní uzly určují hrany V-diagramu, které jsou polopřímkami (případně přímkami). To umožní najít pravoúhelník $R$, ve kterém leží všechny body množiny $P$, všechny vrcholy V-diagramu a zlomové body odpovídající těmto zbývajícím vnitřním uzlům stromu $\mathcal T$.

Průběh algoritmu v nejjednodušší možné situaci množiny tří bodů je demonstrován  následující animací.
\medskip

ANIMACE
\medskip

Přesný popis algoritmu je zachycen v následujících pseudokódech.
\medskip

PSEUDOKÓD 30 z pseudo.pdf
\medskip

PSEUDOKÓD 31 z pseudo.pdf
\medskip

 PSEUDOKÓD 32 z pseudo.pdf
\medskip

\subsection{Časová náročnost}
Nechť množina $P$, pro kterou provádíme algoritmus, má $n$ bodů. Po průchodu první místní událostí ve frontě bude plážová linie tvořena jedinou parabolou. Při průchodu dalšími místními událostmi přibudou vždy maximálně dva oblouky parabol. Proto celkový počet oblouků, které se někdy vyskytnou  v plážové linii nepřevýší $2n-1$. V binárním vyváženém  stromě s maximálně $2n-1$ listy trvají operace
přidání dvou listů a ubrání jednoho listu a případné vyvážení stromu čas
$$O(\log(2n-1))=O(\log n).$$
Protože každý oblouk v plážové linii jednou vznikne a nejvýše jednou zanikne, bude realizovaných událostí
$O(2n-1)=O(n)$. V každé události provedeme konečný shora omezený počet kroků, které trvají konečný čas nebo čas maximálně $O(\log n)$. Tím jsme dokázali:

\begin{thm} Časová náročnost algoritmu zametací přímky pro vytvoření V-diagramu množiny $n$ bodů je $O(n\log n)$. 
\end{thm} 

Implementace algoritmu pomocí Matlabu je provedena v bakalářské práci Jany Tomšů O algoritmech počítačové geometrie dostupné na 

\centerline{https://is.muni.cz/auth/th/175345/prif$\_$b/}



\end{document} 





