% Chapter 10 Delaunay triangulation
\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}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ap}[thm]{Appendix}

\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem{remark}[thm]{Remark}  
\newtheorem{example}[thm]{Example}
\newtheorem*{ack}{Acknowledgement}

\def\R{\mathbb{R}}
\def\d{\operatorname{dist}}

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

\begin{document}

  
\setcounter{section}{9}
\section{\large Delaunay Triangulation}

\subsection*{Motivation}
Let us consider a function $f:\mathbb R^2\to\mathbb R$.  Its values are  known only in the final set of points $P$. One way to approximate such a function is to divide the convex hull of the set $P$ into triangles with vertices at the points of the set $P$ and replace the function $f$ by a function which is linear on these triangles. This means the following: Each point $x$ of a triangle $p_i, p_j, p_k$ is a convex combination of the vertices 
$$x=t_1p_1+t_2p_2+t_3p_3, \quad \text{ where }t_1+t_2+t_3=1,\ t_1\ge 0, \ t_2\ge 0,\ t_3\ge 0,$$
and hence we put
$$f(x)=t_1f(p_1)+t_2f(p_2)+t_3f(p_3).$$
The graph of the approximation of the function $f$ is thus formed by triangles in 
$\mathbb R ^ 2\times\mathbb R$ with vertices
 $(p_i,f(p_i)$, $(p_j,f(p_j)$ and $(p_k,f(p_k))$.
 
\medskip
FIGURE 10.1  Linear approximation of the function $f$.
\medskip

This approximation depends substantially on how we do the triangulation of the convex hull of our set. It seems that a good approximation should be one that has 
no triangles with small angles. We will deal with such triangulations in the following text.

\subsection*{Angle-optimal triangulation}
First, we show that for a given set of points $P$ in a plane, all the triangulations of its convex hull have the same number of triangles. This allows us to compare different triangulations lexicographically according to the sizes of angles.

\begin{thm} Let $P$ be a set of $n$ points in the plane. Let the convex hull of  $P$ have $k$ edges. Then any triangulation of the convex hull of the set $P$ has $2n-2-k$ triangles and $3n-3-k$ edges. 
\end{thm}

\begin{proof} Denote the number of triangles in the triangulation as $m$. Every triangle has three edges. $k$ edges are the edge of only one triangle, the remaining edges are the edges of two triangles. So the number of all edges is equal to
$$h=\frac{3m+k}{2}.$$
The Euler Formula says that
$$n-h+(m+1)=2.$$
Substituting $h$ from the first formula we derive that
$$m=2n-2-k.$$
From here substituting into the first formula we get
$$h=3n-3-k.$$
\end{proof}

Let $\mathcal T$ be a triangulation of the convex hull of a set  $P$ with $m=2n-2-k$ triangles. The triangles of this triangulation have $3m$ angles. Let us order them into a sequence
$$\alpha(\mathcal T)=(\alpha_1, \alpha_2, \dots,\alpha_{3m}), \quad 
\alpha_1\le \alpha_2\le \dots \le \alpha_{3m}.$$
On these sequences we define the lexicographis order
$$\alpha(\mathcal T)<\alpha(\mathcal T'),$$
if there is  $i\in\{1,2,\dots,3m\}$ such that
$$\alpha_j=\alpha'_j \quad \text{ for }j<i \quad \text{ and }\quad \alpha_i<\alpha'_i.$$
A triangulation  $\mathcal T$ is called  {\it angle-optimal} if it is maximal in this ordering.


\subsection*{Legal edges and legal triangulations}
For the purposes of our algorithm which should create a suitable triangulation
we will need the notion of {\it legal edge} a {\it legal triangulation}.
Before we start with a definition we repeat shortly high school geometry, especially what we know about the angles on the arc of a circle.

Consider points $p$ and $q$ on the circle  $\mathcal K$ with a center $s$. The points divide the circle into two arcs. Choose a point $a$ on the first of them and a point $b$
on the second. Denote the angles in the triangles  $paq$ and $pbq$ at the vertices $a$ and $b$ $\alpha$ and $\beta$, respectively. We call them {\it arc angles} of the chord $pq$. Arc angles have these two importatnt properties:
\begin{itemize}
\item The size of angles  $\alpha$ and $\beta$ does not depend on the position of points  $a$ and $b$ on the given arcs.
\item Their sum is $\alpha+\beta=180^o$.
\end{itemize}
From here we can easily derive that every triangle $pcq$ where the point $c$ lies in the halfplane $paq$ inside the circle  $\mathcal K$ has the angle $$\gamma>\alpha$$
at the vertex $c$ and that every triangle $pdq$ where the point $d$ lies in the halfplane $paq$ outside the circle  $\mathcal K$ has the angle
$$\delta<\alpha$$
at the vertex $d$.
\medskip

FIGURE 10.2 Arc angles
\medskip

From the properties of arc angles it can be shown that we can curcimscribe
a circle to a quadrilateral if and only if the sum of opposite angles is equal to $180^o$.

Now consider a triangulation $\mathcal T$ and in it an edge $pq$ which has two adjacent triangles $pqr$ a $pqt$. Such an edge is called {\it illegal edge of the triangulation} $\mathcal T$ if the point $t$ lies inside the circle circumscribed to the triangle $pqr$. It is equivalent to the fact that the sum of angles at vertices $r$ a $t$ in the quadrilateral $prqt$ is greater than $180^o$ and also to the fact that the point $r$ lies inside the circle circumcsribed to the triangle $pqt$.
\medskip

FIGURE 10.3 Illegal edge $pq$.
\medskip

The edges of the triangulation $\mathcal T$ which are not illegal are called
{\it legal} and the triangulation without illegal edges is called  {\it legal triangulation}.
Immediate consequence of this definition is the following characterization of legal triangulations:

\begin{lemma}\label{legal} A triangulation is legal if and only if for every edge $pq$
with adjacent triagles $pqr$ and $pqt$ the point $t$ does not lie inside the circle circumscribed to the triangle $pqr$.
\end{lemma}

The following assertion will play a crucial role in our algorithm.

\begin{lemma} Let $\mathcal T$ be a triangulation with illegal edge $pq$.
Denote the adjacent triangles $pqr$ a $pqt$. From the triangulation $\mathcal T$ let us make a new triangulation  $\mathcal T'$ in such a way that we replace the edge
$pq$ by the new edge $rt$. This edge is legal in the triangulation $\mathcal T'$ 
and moreover in the arrangement defined in the previous section
$$\alpha(\mathcal T)<\alpha(\mathcal T').$$
The exchange of the edge  $pq$ for the edge $rt$ is called  {\it flip}.  
\end{lemma}

\medskip

FIGURE 10.4 Flip
\medskip
 
\begin{proof} Since the edge $pq$ is illegal in the triangulation $\mathcal T$, the sum of the angles at vertices  $r$ and $t$ in the quadrilateral $prqt$ is bigger than $180^o$ and so the sum of the angles at $p$ and $q$ in the same quadrilateral is less than $180^o$. (The sum of all angles in the quadrilateral is $360^o$.)
That is why the edge $rt$ in the triangulation $\mathcal T'$ is legal.

Denote the angles before and after the flip according to the following
figure:
\medskip

FIGURE 10.5 Notation. 
\medskip

Since all the other triangles of both triangulations are the same, for
$$\alpha(\mathcal T)<\alpha(\mathcal T'),$$
it suffices to prove that
$$\min \{\alpha_i,\ i=1,2,\dots,6\}<\min \{\beta_i,\ i=1,2,\dots,6\}.$$ 
We show subsequently that every $\beta_i$ is bigger than an angle $\alpha_j$.
Obviously,
$$\beta _1>\alpha_1\quad\text{ a }\quad \beta_4>\alpha_5.$$
Further, $\beta _2$ is an arc angle over the chord $pr$ in the circle circumscribed
to the triangle $prt$. Since the point $q$ lies outside this circle, we get 
$$\beta_2>\alpha_5.$$
Similarly $\beta _6$ is an arc angle for the chord $pt$ in the circle circumsribed
to the triangle $prt$. Hence
$$\beta_6>\alpha_4.$$
Analogously, using the circle circumsribed to the triangle $qrt$ we can prove that
$$\beta_3>\alpha_1\quad \text{ a }\quad \beta_5>\alpha_2.$$
\end{proof}

\begin{cor}\label{uol}
An angle-optimal triangulation is legal. 
\end{cor}

\begin{proof} If an angle-optimal triangulation had an illegal edge, using the flip of this edge we would have got a triangulation which is bigger in the defined arrangement which would have been a contradiction with the definition of the angle-optimal triangulation.
\end{proof}

Legal triangulations need not be angle-optimal as the following figure shows on the example of two triangulations of the pentagon $p_1p_2p_3p_4p_5$ to which we can circumscribe a circle. Moreover,  $p_1p_2p_3p_5$ is a square and $p_1p_2p_4$ is a isosceles triangle. Both triangulations  $\mathcal T$ and $\mathcal T'$ are legal but because  $\alpha(\mathcal T)<\alpha(\mathcal T')$, the triangulation $\mathcal T$
is not angle-optimal.

\medskip
FIGURE 10.6 The example of legal triangulation which is not angle-optimal.
\medskip

\subsection*{Delaunay graph and triangulation} Besides angle-optimal triangulation and legal triangulation we introduce another notion of Delaunay  triangulation. First we define what {\it Delaunay graph} is.

The Delaunay graph of the set $P$ has $P$ as the set of vertices. Two vertices $p_i$ and $p_j$ are connected by an edge if there is a circle on which these two points are lying and all the other points of the set $P$ lie outside the circle. It means, that the centre of this circle lies on the edge of the Voronoi diagram which separates the cell determined by $p_i$ from the cell determined by  $p_j$. That is why Delaunay graph is dual to the Voronoi diagram.
 
\medskip
FIGURE 10.7 The duality between the Voronoi diagram (dashed) and the Delaunay 
graph (red).
\medskip

\begin{lemma} The Delaunay graph is a planar graph. 
\end{lemma}

\begin{proof} Suppose that  $p_ip_j$ and $p_kp_l$ are two edges of the Delaunay graph which intersect in the inner point. Let the quadrilateral $p_ip_kp_jp_l$ has the sum of angles at the vertices $p_k$ a $p_l$ at least $180^o$. Consider a circle  which has the chord $p_ip_j$ and  $p_k$ lies outside it. Then $p_l$ does not lie outside the circle. (Otherwise the sum of the angles at $p_k$ and $p_l$ would be smaller than  $180^o$.) 
However this is a contradiction with $p_ip_j$ being an edge of the Delaunay graph.
\end{proof}

\medskip
FIGURE 10.8 Illustration of the proof of Lemma 10.5
\medskip

Bounded faces of the Delaunay graph are polygons. Let points
$p_1,p_2,\dots,$ $p_k$ form the vertices of one of these polygons.
This polygon determines a vertex $v$ in the dual graph, i.e. in the Voronoi diagram.
Hence the points $p_1,p_2,\dots,p_k$ have the same distance to the point $v$
and lie on one circle with the center $v$.

\medskip
FIGURE 10.9 The quadrilateral $p_1p_2p_3p_4$ in the Delaunay graph (black) and the Voronoi diagram (red).
\medskip

{\it Delaunay trangulation} is defined as an arbitrary triangulation of these polygons in the Delaunay graph. The Delaunay triangulation need not be determined uniquely.
Nevertheless, the centres of the circles circumscribed to the triangles in the Delaunay triangulation form the set of the vertices of the Voronoi diagram.
 
\medskip
FIGURE 10.10 Delaunay graph (black) and Delaunay triangulation (black and red).
\medskip

If no four points of the set  $P$ lie on one circle then the Delaunay graph is already the Delaunay triangulation. In this case the Delaunay triangulation is determined
uniquely. We say that in this case the points of the set $P$ are in general position.


Every Delaunay triangulation can be characterized by the following property.

\begin{lemma} A triangulation of the convex hull of the set  $P$ is  Delaunay if and only if for every its edge  $p_ip_j$ holds: the circle circumscribed to an adjacent triangle $p_ip_jp_k$ does not contain any other point of $P$ in its interior.
\end{lemma}

\begin{proof} To the proof we use the duality between the Delaunay graph and the Voronoi diagram.

Let a triangulation is Delaunay. Then the triangle $p_ip_jp_k$ has come into being
by dividing a polygon of the Delaunay graph into triangles.
The centre of the circle circumscribed to the triangle $p_ip_jp_k$ is also the centre of this polygon and the vertex in the Voronoi diagram. That is why in the interior of this circle cannot lie any other point of the set  $P$.

On the contrary, suppose that all edges of a triangulation have the property 
described in the statement. Consider a triangle $p_ip_jp_k$ and the circle circumscribed to it.  No remaining point of $P$ lies in the interior of this circle.
Some of them can lie on the circle. So the triangle $p_ip_jp_k$ is a part of polygon having the same circumscribed circle. It is easy to see that to every edge of this polygon there is a circle having the edge as a chord and having all the other points
of $P$ outside. So the edges of the polygon are the edges of the Delaunay graph
and our triangulation come into being by the triangulation of the Delaunay graph, so it is Delaunay.
\end{proof}

Using this lemma and the characterization of legal triangulations by  Lemma 
\ref{legal}, we get immediately that every Delaunay triangulation is legal.
To prove that every legal triangulation is Delaunay is a little bit more complicated. 

\begin{thm} The set of legal triangulations is equal to the set of Delaunay triangulations. 
\end{thm} 

\begin{proof} Let us prove by contradiction that every legal triangulation is Delaunay. Let $\mathcal T$ be a legal triangulation which is not  Delauney. In this triangulation
there is a triangle $p_ip_jp_k$ and a point $p_l$ such that $p_l$ lies in the interior of the circle circumsribed to $p_ip_jp_k$ and the angle $\angle p_ip_lp_j$ is maximal
for all such triangles and points. Let $p_ip_jp_m$ be an adjacent triangle to the triangle $p_ip_jp_k$ in the triangulation $\mathcal T$. Since this triangulation is legal
the point $p_m$ does not lie in the interior of the circle $\mathcal K$ circumscribed to the triangle $p_ip_jp_k$. The point $p_l$ cannot lie inside the triangle  $p_ip_jp_m$. Let $p_l$ lies on the opposite side of the line $p_jp_m$ than the point $p_i$. From the following figure we can see that for the sizes of agles we have 
$$\angle p_mp_lp_j>\angle p_ip_lp_j$$
which contradicts the choice of the triangle $p_ip_jp_k$ and the point $p_l$.
\end{proof}

\medskip
FIGURE 10.11 To the proof of Theorem 10.7
\medskip


From here and from Corollary \ref{uol} we get:
\begin{cor} 
\begin{enumerate}
\item Every angle-optimal triangulation is Delaunay.
\item If the points of a set  $P$ are in general position, there is just one 
Delaunay triangulation, just one legal triangulation and just one angle-optimal triangulation and these triangulations are the same.
\end{enumerate}
\end{cor}





\subsection*{Basic idea of randomized incremental algorithm} One possibility how to construct algorithmically  Delaunay triangulation is to use algorithm for 
the Voronoi diagram,  to find the dual graph to it and divide its polygons into triangles.

We will present a differnt approach based on the fact that every legal triangulation is Delaunay and which insists in removing gradually illegal edges.

A naive version of such an algorithm is following: Make a triangulation of the convex hull of the set $P$ and go through its edges.  When you find an illegal edge, replace it with a legal edge by a flip and proceed by the same way further. This process is finite because after every flip we get a triangulation which is bigger than the previous one
in described lexicographic order. The number of triangulations is finite, so this process
must sometimes end.

A sofisticated version of this approach is the following randomized incremental algorithm. Its basic idea can be captured in several points:
\begin{enumerate}
\item We denote the point from the set $P$ maximal in lexicographis order first with respect $y$-coordinate and then $x$-coordinate as $p_0$. We add points $\pj$ and $\pd$ to the points of the set $P$  so that all other points of $P$ lie inside the triangle $p_0\pj\pd$.
\item We order these points randomly into a sequence $p_1,p_2,\dots,p_n$. 
Gradually for  $r=1,2,\dots,n$ we add the point $p_r$ to a legal triangulation 
$\mathcal T_{r-1}$ of the triangle $p_0\pj\pd$ where the vertices of single triangles are
in the set 
$$\pd,\pj,p_0,p_1,\dots,p_{r-1}.$$
\item  Using a simultaneously constructed search structure we find 
in which triangle  $p_ip_jp_k$ of the triangulation  $\mathcal T_{r-1}$ the point $p_r$ lies and if it lies in the interior or on the edge. 
Then we connect  the point $p_r$ by edges with vertices of this triangle (if it lies in the interior) or with vertices of adjacent triangles (if it lies on an edge).
This newly created triangulation of the triangle $p_0\pj\pd$ with vertices
in the set  
$$\{\pd,\pj,p_0,p_1,\dots,p_{r-1},p_r\}$$
can be "legalized" using flips which exchange illegal edges for legal ones.
After removing all illegal edges we get a triangulation $\mathcal T_r$.
\item At the end we remove the points $\pj$ and $\pd$ and the edges going from these points from the legal  triangulation $\mathcal T_n$,  Due to a suitable choice of the points  $\pj$ and $\pd$ the remaining triangulation is the legal and  also Delaunay triangulation of the convex hull of the set $P=\{p_0,p_1,p_2,\dots,p_n\}$.
\end{enumerate}

\medskip
FIGURE 10.12 The set $P$ in the triangle $p_0\pj\pd$.
\medskip  

Now we describe the single steps in more details. We start with 
(2) and (3).

\subsection*{Legalization} Let us consider a legal triangulation  $\mathcal T_{r-1}$ described in the step (2) above. If we find using a search structure that the point $p_r$ lies in the interior of a triangle $p_ip_jp_k$, we connect it with single vertices by edges.

\medskip
FIGURE 10.13 The point $p_r$ in the interior of a triangle $p_ip_jp_k$.
\medskip 

 This will create a new triangulation. What is important is that the newly added edges based on $p_r$ are legal. This can be proved as follows: Let $\mathcal K$ be a circle
 circumscribed to the triangle $p_ip_jp_k$.
Since the triangulation  $\mathcal T_{r-1}$ is legal and hence also Delaunay, there is no point from the set $P_{r-1}=\{\pd,\pj, p_0,\dots,p_{r-1}\}$ in the interior of  $\mathcal K$. Let $\mathcal L$ be a circle homothetic to $\mathcal K$ which has the cord $p_rp_i$. See  Figure 10.14. In the interior of this circle there are no points from
$P_{r-1}$. So the edge $p_rp_i$ is an edge of the Delaunay graph for the set
$P_r$ and this has to be legal. Analogously, one can prove that also the edges $p_rp_j$ and $p_rp_k$ are legal.

\medskip
FIGURE 10.14 To the proof that  $p_rp_i$ is legal.
\medskip

It can happen that some of the edges  $p_ip_j$, $p_ip_k$ a $p_jp_k$ become illegal
in the new triangulation. Using a flip we can replace them by  edges going from the point $p_r$. For example let $p_ip_j$ be illegal. Then it is the edge not only of the triangle $p_ip_jp_r$ but elso of an adjacent triangle $p_ip_jp_l$. We replace it by the edge $p_rp_l$ which is already legal.  Now some of the edges $p_ip_l$ and $p_jp_l$ can become illegal. That is why we have to replace it by a flip with an edge based in
the point $p_r$. 

\medskip
FIGURE 10.15 The edge $p_ip_j$ is  illegal.
\medskip

We proceed in this way as long as there is no illegal edge. (After every flip
the new triangulation is bigger in the lexicographic order
than the previous one.)
The procedure is captured in the following animation and pseudocode. The input is the point $p_r$, the edge $p_ip_j$ and a legal triangulation $\mathcal T_{r-1}$.

\medskip
ANIMATION
\medskip

PSEUDOCODE Legalize($p_r$, $p_ip_j$, $\mathcal T_{r-1}$) from pseudo.pdf, page
37,  but use the form from the  Czech version of e-learning.
\medskip  

If we find  that the point $p_r$ lies on an edge $p_ip_j$, then we replace the edge 
$p_ip_j$ by the edges  $p_rp_i$ and $p_rp_j$ and we create new edges connecting the point $p_r$ with the vertices  $p_k$ and $p_l$ of adjacent triangles to the edge
$p_ip_j$. Similarly as above one can show that the new edges
$p_rp_i$, $p_rp_j$, $p_rp_k$ a $p_rp_l$ are legal.
However the edges $p_ip_k$, $p_jp_k$, $p_ip_l$ a $p_jp_l$ can become illegal. This can be corrected by making gradually flips as in the above case.

\medskip
FIGURE 10.16 The point $p_r$ on the edge $p_ip_j$.
\medskip  

\subsection*{Search structure} 
In the course of the algorithm we have a relevant search structure for every triangulation.  This is an oriented graph the leaves of which are the triangles
of the actual triangulation and inner nodes are the triangles of the previous triangulations.

At the beginning the triangulation $\mathcal T_0$ has the only triangle
$p_0\pj\pd$ and the corresponding search structure  $\mathcal D_0$ has only one node given by this triangle. For the triangulation  $\mathcal T_{r-1}$ we have a search structure  $\mathcal D_{r-1}$. We change the triangulation $\mathcal T_{r-1}$ gradually in the way described in the previous section. Simultaneously we change the search structure. To every transition in the triangulation there is a corresponding transition from one search structure to further search structure.
This is illustrated in the Figure 10.17.

\medskip
FIGURE 10.17 The change of the search structure corresponding to newly added edges inside a triangle.
\medskip
 
FIGURE 10.18 The change of the serch structure corresponding to a flip.
\medskip

Using this procedure we create a search structure $\mathcal D_r$ corresponding
to the legal triangulation $\mathcal T_r$. The resulting search structure depends only on the random order of the points $p_1,p_2,\dots,p_r$.  

\subsection*{Initial choice of points $p_0$, $p_{-1}$, $p_{-2}$}
Now let us explain the steps (1) and (4) of our algorithm. We will refer to the geometric idea for better understanding.
Important is that the points $\pj$ a $\pd$ will be determined by their properties, we will not determined their concrete coordinates. The decisions whether some edge is legal or illegal, if among four points, which are considered, is some of the points $\pj$, $\pd$, will not be made by computations but only  by applying the rules which follow from the properties of  $\pj$ a $\pd$.

As we have already said for the point $p_0$ we choose that one from 
 $P$ which is maximal in the lexicographic order first with respect to the coordinate $y$ and then with respect to the coordinate $x$. 

We choose the point $\pj$ to the right of the set  $P$ and under it. (More exactly:
its  $y$-coordinate is smaller than the minimum of $y$-coordinates of the points from   $P$ and its $x$-coordinate is bigger than the maximum of $x$-coordinates of the points from $P$.)
The choice of $\pj$ is carried out so that  
\begin{itemize}
\item it lies outside all circles circumscribed to all triples of points from 
 $P$ which do not lie in one line,
\item all  points $p_i$ with $i>0$  lie under the line $p_0\pj$.
\end{itemize}

We choose the point $\pd$ to the left of the set $P$ and over it so that
\begin{itemize}
\item  it lies outside all circles circumscribed to all triples of points from 
 $P\cup\{\pj\}$ which do not lie in one line,
\item all  points $p_i$ with $i>0$  lie under the line $p_0\pd$,
\item all points $p_i$ with $i\ge 0$  lie over the line $\pj\pd$.
\end{itemize}
So all the points $p_i$ with $i>0$  lie in the interior of the triangle
$p_0\pj\pd$ and every quadrilateral 
$\pd p_i \pj p_j$ is not convex which implies that the point $\pj$ lies outside all circles circumscribed to the triangles $\pd p_i p_j$.
\medskip

FIGURE 10.19 The set  $P$ in the triangle $p_0\pj\pd$.
\medskip

Under these assumptions every Delaunay (legal) triangulation of $P\cup\{\pj,\pd\}$
consists of 
\begin{enumerate}
\item the edges going from the point $\pj$ to the vertices of the right hand side of the convex hull of the set $P$,
\item the edges going from the point $\pd$ to the vertices of the left hand side of the convex hull of the set $P$,
\item a Delaunay triangulation of the set $P$. 
\end{enumerate}
Consequetly we can obtain a Delaunay triangulation of the set $P$ in the way descrobed in the step (4).

The rules how to work with our algorithm are based on the following lemma:

\begin{lemma} \label{ekv} If the points $p_0$, $\pj$ a $\pd$ are chosen as described above the following assertions are equivalent:
\begin{itemize}
\item $p_j$ lies to the left of the oriented line $p_i\pj$. 
\item $p_j$ lies to the left of the oriented line $\pd p_i$.
\item $p_j>p_i$ in the lexicographic order first with respect to $y$ and then with respect to $x$.
\end{itemize}
\end{lemma}
Instead of doing a proof we demonstrate the situation by a picture.
\medskip


\medskip
FIGURE 10.20 To  Lemma \ref{ekv}. The points $\pj$ and $\pd$ are chosen in such a way that in the coloured angles there is no other point of the set $P$.
\medskip

When finding weather an edge is legal or illegal we use the following rules:
\begin{itemize}
\item All edges of the triangle $p_0\pj\pd$ are legal.
\item The edge  $\pd p_j$ with adjacent vertices  $\pj$ and $p_k$ is legal.
\end{itemize}

\medskip
FIGURE 10.21 Illustration of the previous statement.
\medskip
\medskip

\begin{itemize}
\item The edge $\pj p_j$  with adjacent vertices $\pd$ and $p_k$ is legal.
\item Let the edge $p_i p_j$ have adjacent vertices  $p_k$ and $p_l$, let the quadrilateral $p_ip_kp_jp_l$ 
be convex and let there be just one negative number among the numbers $i,j,k,l$. Then the edge
$p_ip_j$ is legal if and only if 
$$\min(k.l)<\min(i,j).$$  
\end{itemize}

\medskip
FIGURE 10.22 $\min(-2,l)<\min(i,j)$, the edge  $p_ip_j$ is legal.

\medskip
FIGURE 10.23 $\min(k,l)>\min(-1,j)$, the edge $\pj p_j$ is  illegal.
\medskip

\subsection*{Pseudocode of the algorithm and its expected time complexity}A brief pseudocode of the algorithm described in details in the previous sections can look like this:

\medskip
PSEODOCODE DelaunayTriangulation($P$) from pseudo.pdf, page 36 
\medskip

Without proof we give the following statement about expected time complexity of the algorithm.
See  [Berg et al] for the proof.

\begin{thm} Expected time complexity of the randomized incremental algorithm for the Delaunay triangulation of the set with $n+1$ elements is $O(n\log n)$. 
\end{thm}
\end{document} 

