Fermeture du graphe de distance

Dans le problème de satisfaction de contraintes de distance, il y a deux types données : d'une part les coordonnées des points, pour lesquels on veut obtenir un filtrage optimal des domaines et d'autre part les distances. Ces dernières ne garantissent pas toujours l'existence de solutions, il faut que pour tout triplet de points les inégalités triangulaires soient vérifiées. Grace à ces contraintes supplémentaires on peut borner les distances inconnues en utilisant les distances données et le système d'inégalités, ce qui revient à compléter le graphe de distance.

Figure: Fermeture du graphe de distance associé à l'exemple 1.1

La valuation des arètes du graphe complet peut être calculée en résolvant le $\mathcal{CSP}$, qu'on notera INEQ( $\mathcal{I}$), dont les inconnues sont les distances entre les points, les domaines sont ceux de ces distances, et les contraintes sont exprimées par l'ensemble de toutes les inégalités triangulaires du système :

$$\forall i,j,k \in [1..n]: i \neq j \neq k \left\{ \begin{tabular}... ...$\delta_{i,j} \geq \vert\delta_{i,k} - \delta_{j,k}\vert$} \end{tabular}\right.$$

Étant donnée une instance quelconque $\mathcal{I}=(\mathcal{P},\:\mathcal{D},\:\Delta)$, on peut donc toujours construire l' instance complète de $\mathcal{I}$ en calculant la fermeture du graphe de distance qui lui est associé.
Pour chaque arête d'un triangle donné on a 2 contraintes, ce qui fait 6 contraintes par triangle. Pour $n$ points donnés, on dénombre $\frac{n(n-1)(n-2)}{6}$ triangles, y compris les triangles dégénérés si certains points sont confondus. Donc :

• le nombre de contraintes est $n(n-1)(n-2)$
• le nombre de variables est $\frac{n(n-1)}{2}$

Puisque ce sont des contraintes linéaires, on peut utiliser l'algorithme du simplexe, pour résoudre INEQ( $\mathcal{I}$).

La fermeture du graphe de distance nous garantit donc que tous les triangles du système sont constructibles, quelles que soient les valeurs choisies dans les domaines des distances entre ses sommets. Autrement dit on a une consistance de chemin réduite aux bornes des domaines des distances sur INEQ( $\mathcal{I}$). Or, cela n'implique pas qu'un polygône ayant plus de 3 côtés soit constructible. Par exemple, le quadrilatère $ABCD$ n'est pas constructible si on choisit $AC=7$ et $BD=6$. En effet cela implique que $A$, $C$ et $D$ sont alignés car $AC=AD+CD$, et d'autre part que $B$, $C$ et $D$ sont alignés car $BD=BC+CD$. Donc $A$, $B$, $C$ et $D$ sont alignés, pourtant aucune longueur n'est égale à la somme des 2 autres dans le triangle $ABC$, ce qui est incohérent.