Formule de calcul

On cherche à triangulariser des polygones de manière optimale. Pour cela on va utiliser la méthode par programmation dynamique. On va donc chercher à établir une formule de calcul sous forme d'une récurrence complète.

On cherche la taille optimale de la triangularisation, on peut donc déjà dire que la formule de récurrence sera de la forme:

$$T_{i,t}=\min(...)$$

Les $...$ restant à déterminer.
Préalablement à tout début de calcul, nous avons besoin de la valeur de toutes les cordes qu'il est possible de réaliser dans le polygone considéré. A cette fin nous allons remplir un tableau $lgCorde[n][n]$, avec $n$ le nombre de sommets du polygone, tel que:

$$\forall i,j \in \{1..n\}, \;lgCorde[i][j]=distance(s_i,s_j)$$

Ensuite, nous allons mettre en équation le problème.
Soit le sous-problème $T_{i,t}$ de taille $t$ débutant au sommet $s_i$. Selon l'énoncé, la résolution de sous-problème de taille inférieure à trois ne demande aucune action; donc on peut en déduire que:

$$\forall i<t,\;\forall t \in \{1..3\}, \;T_{i,t}=0$$

Dans les autres cas, pour résoudre $T_{i,t}$, on va considérer les trois options suivantes présentées dans l'énoncé:

1. $T_{i,t}=lgCorde[s_{i}][s_{i+t-2}]+lgCorde[s_i][s_{i+t-1}]+ lgCorde[s_i][s_{i+t-2}]+T_{i,t-1}$
2. $T_{i,t}=lgCorde[s_i][s_{i+t-1}]+lgCorde[s_{i+1}][s_{i+t-1}]+ lgCorde[s_i][s_{i+1}]+T_{i+1,t-1}$
3. $T_{i,t}=lgCorde[s_i][s_{i+k}]+lgCorde[s_{i+k}][s_{i+t-1}]+T_{i,k+1}+ T_{i+k,t-k}$

Figure 2: Schéma du polygone avec deux cordes partant de $s_i$

On voit bien que pour calculer $T_{i,t}$, on va avoir besoin du calcul de $T_{i,k+1}$ et de $T_{i+k,t-k}$. De plus, les deux premières options sont des cas particuliers de la troisième. Mais en prenant en compte le fait que l'on calcule l'indice d'un sommet modulo le nombre de sommets du polygone.
Pour cela, on va faire varier l'indice $k$ sur l'intervalle $[i+1,i+t-2]$. Mais deux cas particuliers se dégagent:

• $k=1$: on considère une arête du polygone, donc $T_{i,2}=0$ et $lgCorde[s_i][s_{i+1}]=0$
• $k=2$: on considère encore une fois une arête du polygone,
  donc $T_{i+t-2,2}=0$ et $lgCorde[s_i][s_{i+t-2}]=0$

On peut donc généraliser sous la forme:

$$T_{i,t} = \min(lgCorde[s_i][s_{(i+k)\bmod(n)}]+ lgCorde[s_{(i+k)\bmod(n)}][s_{(i+t-1)\bmod(n)}]+T_{i,k+1}+T_{i+k,t-k})$$

$$\forall k,\; 2\leq k \leq t-3$$

$$T_{i,t} = lgCorde[s_{i+1}][s_{i+t-1}]+T_{i+1,t-1}, k=1$$

$$T_{i,t} = lgCorde[s_{i}][s_{i+t-2}]+T_{i,t-2+1}, k=2$$