Modifications éventuelles

On est sûr de toujours couvrir de manière systématique l'ensemble des sommets du polynomes puisque le sommet de départ sert de base pour la décomposition du problème en deux sous-problèmes.

Dans le cas où l'on tire deux cordes quelconques, il conviendrait de vérifier plusieurs choses:

• les deux cordes ne doivent pas se couper
• aucune des deux cordes ne doivent relier deux sommets consécutifs

Figure 3: Schéma du polygone avec deux cordes aléatoires

Dans le schéma de la figure 3, les deux cordes sont représentées par ( $s_i,s_{i+k}$) et ( $s_j,s_{j+l}$) et elles délimitent trois sous-polynomes $(1)$, $(2)$ et $(3)$. Ces polynomes deviennent les nouveaux sous-problèmes de la triangularisation.

Le précédent algorithme devrait être modifié pour prendre en compte la récurrence de la triangularisation sur, non plus deux sous-problèmes, mais trois. Ce qui pourrait nous donner quelque chose comme:

$$T_{i,t}=\min(T_{i,i+k}+T_{j,j+l}+T_{nouveau\_polygone}+cout(cordes\_tracees))$$

Mais le précédent algorithme considérait les sommets consécutivement. Sous ces nouvelles conditions, un des polygones n'a pas tous ses côtés consécutifs. L'appel à $T_{nouveau\_polygone}$ ne sera pas le même que dans les deux autres cas, il faudra considérer cette partie comme un nouveau polygone.