\documentclass{beamer}

\usepackage{beamerthemesplit}
%\usetheme{Warsaw}
\usetheme{Hannover} % Similar to the default 
\usecolortheme{default}

\usepackage[latin1]{inputenc}% 
\usepackage[T1]{fontenc}% 
\usepackage[francais]{babel}% 
\uselanguage{French}
\languagepath{French}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{times}

\usepackage{graphicx}

\newcommand{\R}{\mathbb{R}}

\newtheorem{algorithm}{LOP (\emph{Local Optimization Procedure})}
\newtheorem{preuvetheo}{Preuve du ThÃ©orÃ¨me}
%\renewcommand{\theorem}{ThÃ©orÃ¨me}
%\renewcommand{\definition}{DÃ©finition}
%\renewcommand{\corollary}{Corollaire}
%\renewcommand{\lemma}{Lemme}

\title{\emph{Minimal roughness property of the Delaunay triangulation} \\ \texttt{Samuel RIPPA}}

\author{Alexandra PIMENTA DOS SANTOS}
\date{10 Mai 2012}

\begin{document}
\maketitle

\begin{frame}
\frametitle{Table des MatiÃ¨res}
\tableofcontents
\end{frame}

\section{DÃ©finitions et Notations}

\begin{frame}
 \begin{center}
  \large{\color{blue}DÃ©finitions et Notations}
 \end{center}
\end{frame}


\begin{frame}
Soit $D=\{ \left( x_i,y_i,F_i \right) \}_{i=1}^{i=N}$ un ensemble de donnÃ©es dispersÃ©es, avec $V=\{ v_i=\left( x_i, y_i\right)\}_{i=1}^{i=N}$ des 
points non colinÃ©aires de $\R^2$. On pose $H_V$ l'envelope convexe de V.
\pause\begin{definition}
 Un ensemble $T=\{T_i\}_{i=1}^{i=nt}$ de triangles, ouverts, non dÃ©gÃ©nÃ©rÃ©s est une triangulation de $H_V$ si:
\begin{itemize}
\pause \item $V$ est l'ensemble de tous les sommets des triangles de $T$.
\pause \item Toutes les arrÃªtes d'un triangle de T ont seulement deux points de $V$.
\pause \item $\overline H_V = \cup_{i=1}^{nt} \overline T_i$, $T_i \cap T_j = \varnothing$, $\forall i \neq j$. 
\end{itemize}
\end{definition}
\end{frame}

\begin{frame}
\begin{definition}
 Soit $D$ comme avant et $T$ une triangulation de $H_V$. On dÃ©finit $S_1^0\left(T\right)$ comme Ã©tant l'ensemble des fonctions linÃ©aires 
par morceaux dÃ©finies sur T, c.a.d., 
\begin{center}
 $S_1^0\left(T\right) = \{g \in C^0\left(H_V\right) : g|_{T_i} \in \prod_1\}$
\end{center}
oÃ¹ $\prod_1$ est l'espace tri-dimensionnel de polynÃ´mes linÃ©aires. 
\end{definition}
\pause\begin{definition}
 La Surface d'Interpolation Linaire par Morceaux, (PLIS - \emph{Piecewise Linear Interpolation Surface}), pour un certain vecteur de 
donnes $F=\left(F_1, \ldots, F_N\right)$ est l'unique fonction $f_T \in S_1^0$ qui interpole $F$, c.a.d., $f_T\left(x_i,y_i\right) = F_i \ \forall i=1,\ldots,N$.
\end{definition}
\end{frame}

\begin{frame}
\begin{definition}
 On dÃ©finit la rugositÃ© d'un vecteur de donnÃ©es $F$, par rapport Ã  la triangulation $T$, comme Ã©tant $R\left(F,T\right) = {\mid f_T 
\mid}_{T,1}$, avec ${\mid . \mid}_{T,1}$ la semi-norme $H^1$.
\end{definition}
\pause

Avantages de la triangulation de Delaunay:
\begin{itemize}
\pause \item bonnes propries gomtriques:
 \begin{itemize}
\pause \item maximisation du plus petit angle de la triangulation et l'erreur d'interpolation croÃ®t avec la dÃ©croissance du plus petit 
angle;
\pause \item est assez proche de la triangulation qui minimise le plus grand angle, plus cet angle approche $\pi$, plus l'erreur est grand;
 \end{itemize}
\pause \item algorithmes efficaces pour sa construction.
\end{itemize}
\end{frame}


\section{ThÃ©orÃ¨me Principal}

\begin{frame}
 \begin{center}
  \large{\color{blue}ThÃ©orÃ¨me Principal}
 \end{center}
\end{frame}


\begin{frame}
 \begin{theorem}
  Soit $V$ comme prÃ©cÃ©demment et $T^*$ une triangulation de Delaunay de $H_V$. Alors, $R\left(F,T^*\right) \leq R\left(F,T\right)$ pour 
toute triangulation $T$ de $H_V$ et tout le vecteur $F=\left( F_1, \ldots,F_N\right)$. 
 \end{theorem}

\pause
\begin{figure}[h!]
\includegraphics[scale=0.5]{diagonals.jpg}
\caption{Changement des diagonals par le critÃ¨re du cercle. On note $Q$ le quadrilatÃ¨re strictement convex formÃ© par les 2 triangles de 
$T$ ayant $e$ comme arÃªte commune.}
\end{figure}
\end{frame}

\begin{frame}
\begin{definition}
 Le critÃ¨re du cercle transforme la triangulation $T$ en $T'$ si et seulement si le cercle qui passe par les trois sommets de n'importe 
quel triangle (de $T$) qui forment Q contient Ã  l'intÃ©rieur le sommet qui reste.
\end{definition}
 \pause
\begin{definition}
 \begin{itemize}
  \item Une arÃªte $e$ est localement optimale si l'application du critÃ¨re du cercle Ã  cet arÃªte ne la change pas.
\pause \item Une triangulation est localement optimale si toutes ses arÃªtes sont localement optimales.
 \end{itemize}
\end{definition}
\pause
\begin{exampleblock}{Remarque}
 Une triangulation $T$ est de Delaunay si et seulement si elle est locallement optimale par rapport au critÃ¨re du cercle. 
\end{exampleblock}
\end{frame}

\begin{frame}
 \begin{algorithm}
  \begin{enumerate}
\pause   \item On construit une triangulation $T^{\left(0\right)}$ de $H_V$ et on pose $T \leftarrow T^{\left(0\right)}$
\pause \item Si $T$ est localement optimale, on fini l'algorithme. Sinon on passe Ã  l'Ã©tape 3.
\pause \item Soit $e$ une arÃªte interne de $T$ non localement optimale et $Q$ comme avant.
\begin{itemize}
\pause \item On change les diagonales de $Q$: on remplace $e$ par $e'$.
\pause \item On pose $T \leftarrow T'$ et on revient Ã  l'Ã©tape 2. 
\end{itemize}
\end{enumerate}
\end{algorithm}

\pause
L'algorithme proposÃ© par Lawson conduit, en un nombre fini de changements, Ã  une triangulation localement optimale, donc de Delaunay, $T^*$.

\end{frame}

\begin{frame}
 
\begin{figure}[h!]
\includegraphics[scale=0.5]{fig2.jpg}
\end{figure}
\pause
On dÃ©finit $r_i = d(v_i, v_0)\text{, }i=1,\dots,4$.
\pause
\begin{lemma}
 Le critÃ¨re du cercle remplace $e$ par $e'$ ssi $r_2r_4 < r_1r_3$.
\end{lemma}
\end{frame}

\begin{frame}
\begin{figure}[h!]
\includegraphics[scale=0.35]{cycliques.jpeg}
\end{figure}

\pause
\begin{lemma}
 Soit $f_T \in S^0_1(T)$ et $f_{T'} \in S^0_1(T')$. Alors, ${\mid f_T \mid}_{T,1}^2-{\mid f_T' \mid}_{T',1}^2 = A(r_1r_3-r_2r_4)$\\
oÃ¹ $A=(f_T(x_0,y_0)-f_{T'}(x_0,y_0))^2 \left( \frac{(r_1+r_3)(r_2+r_4)}{2r_1r_2r_3r_4\sin\theta} \right) \text{, }\theta=\angle v_1v_0v_2$.
\end{lemma}

\end{frame}

\begin{frame}
 \begin{lemma}
  Soit $e$ une arÃªte d'une triangulation $T$ qui peut Ãªtre changÃ©e par le critÃ¨re du cercle et $T'$ la triangulation rÃ©sultante. Alors,\\
$R(F,T')\leq R(F,T)$ pour tout vecteur de donnÃ©es $F$.
 \end{lemma}

\pause
\begin{corollary}
 Si les points $(x_k, y_k,F_k)\in \R^3$, $k=1,2,3,4$, ne sont pas coplanaires, alors le critÃ¨re de rugositÃ© et le critÃ¨re du cercle 
sont Ã©quivalents.
\end{corollary}

\pause
\begin{lemma}
 Pour n'importe quelles deux triangulations de Delaunay $T^1$ et $T^2$ et n'importe quel vecteur de donnÃ©es $F$, on a
$R(F, T^1)=R(F, T^2)$.
\end{lemma}

\end{frame}

\begin{frame}
 \begin{preuvetheo}
  \begin{enumerate}
   \item On prend $T'$ une triangulation qui minimise le critÃ¨re de rugositÃ©;
   \pause \item On suppose qu'il existe $T^d$ de Delaunay qui ne minimise pas ce critÃ¨re;
   \pause \item On applique le LOP et on transforme $T'$ en $T^*$, de Delaunay;
   \pause \item $R(F,T^*)\leq R(F,T')$, par le lemme;
   \pause \item $R(F,T^*)=R(F,T^d)$, par le lemme $\Rightarrow R(F, T^d)\leq R(F, T')$ \bf{Contradiction!}
  \end{enumerate}
 \end{preuvetheo}
\pause
 \begin{exampleblock}{Attention}
 Une triangulation qui minimise le critÃ¨re de rugositÃ© n'est pas forcÃ©ment de Delaunay! Si on prend $F=(1,\dots,1)$, $R(F,T)=0$, pour 
toute triangulation $T$.
 \end{exampleblock}
\end{frame}

\begin{frame}
 \begin{corollary}
  Si on n'a pas 4 points de l'ensemble $D=\{x_i,y_i,F_i\}^N_1$ coplanaires, alors une triangulation $T'$ minimise le critÃ¨re 
de rugositÃ© ssi $T'$ est une triangulation de Delaunay.
 \end{corollary}
 \pause
 \begin{corollary}
 Si on n'a pas 4 points de l'ensemble $V=\{(x_i,y_i)\}^N_1$ cocycliques et on n'a pas 4 points de $D$ coplanaires, alors 
la triangulation qui minimise le critÃ¨re de rugositÃ© est unique.
 \end{corollary}
\end{frame}

\section{Conclusions et Remarques}

\begin{frame}
 \begin{center}
  \large{\color{blue}Conclusions et Remarques}
 \end{center}
\end{frame}

\begin{frame}
 \begin{itemize}
  \item La triangulation de Delaunay minimise le critÃ¨re de rugositÃ©;
\pause \item Elle est utlisÃ©e pour des schÃ©mas des discrÃ©tisations polynomiales due a ces bonnes propriÃ©tÃ©es gÃ©omÃ©triques.
 \end{itemize}
\pause
\begin{exampleblock}{Remarque}
 En 1990, le concept de \emph{Triangulation dÃ©pendente des donnÃ©es} a Ã©tÃ© introduit et plusieurs tests numÃ©riques ont montrÃ© que la 
triangulation de Delaunay n'est pas toujours le bon choix pour l'interpolation linÃ©aire.
\end{exampleblock}

\end{frame}

\begin{frame}
 \begin{exampleblock}{}
 Les triangulations de Delaunay sont bonnes pour approximer des fonctions qui minimisent la semi-norm $H^1$ dans le bon espace 
fonctionnel. Ceci est le cas des fonctions harmoniques satisfaisant l'Ã©quation de Laplace $\Delta g = 0$.
\end{exampleblock}
\end{frame}

\end{document}