Trace de la 2B-consistance

Exemple 3.1 (Trace de la 2B-consistance)   Reprenons le CSP défini dans l'exemple 1.1].
On a : $Q$={$<C_2,x_C>$, $<C_2,x_D>$, $<C_2,y_C>$, $<C_2,y_D>$, $<C_1,y_C>$, $<C_3,y_D>$, $<C_3,x_D>$, $<C_1,x_C>$ }.

1. $<C_2,x_C>$ : $x_C = x_D \pm \sqrt{16 - {(y_C-y_D)}^2}$.
   Projection des domaines $D_{x_C}$ = $D_{x_C} \cap ( D_{x_D} + \sqrt{[16,16] - {(D_{y_C} - D_{y_D})}^2}$
   $D_{x_C}=[6,10] \cap ( [-3,3] + \sqrt{[16,16] - {( [-2,2] - [-3,3] )}^2})$
   $D_{x_C}=[6,10] \cap ( [-3,3] + \sqrt{[16,16] - {[-5,5]}^2})$
   $D_{x_C}=[6,10] \cap ( [-3,3] + \sqrt{[16,16] - [0,25]})$
   $D_{x_C}=[6,10] \cap ( [-3,3] + \sqrt{[-9,16]})$
   $D_{x_C}=[6,10] \cap ( [-3,3] + [-4,4] )$
   $D_{x_C}=[6,10] \cap [-7,7]$
   $D_{x_C}=[6,7]$
   donc $Q$={$<C_2,x_D>$, $<C_2,y_C>$, $<C_2,y_D>$, $<C_1,y_C>$, $<C_3,y_D>$, $<C_3,x_D>$, $<C_1,x_C>$}.
2. $<C_2,x_D>$ : $x_D = x_C \pm \sqrt{16 - {(y_C-y_D)}^2}$.
   Projection des domaines $D_{x_D}$ = $D_{x_D} \cap ( D_{x_C} + \sqrt{[16,16] - {(D_{y_C} - D_{y_D})}^2}$
   $D_{x_D}=[-3,3] \cap ( [6,7] + \sqrt{[16,16] - {( [-2,2] - [-3,3] )}^2})$
   $D_{x_D}=[-3,3] \cap [2,11]$
   $D_{x_D}=[2,3]$
   donc $Q$={$<C_2,y_C>$, $<C_2,y_D>$, $<C_1,y_C>$, $<C_3,y_D>$, $<C_3,x_D>$, $<C_1,x_C>$, $<C_2,x_C>$}.
3. $<C_2,y_C>$ : $y_C = y_D \pm \sqrt{16 - {(x_C-x_D)}^2}$.
   Projection des domaines $D_{y_C}$ = $D_{y_C} \cap ( D_{y_D} + \sqrt{[16,16] - {(D_{x_C} - D_{x_D})}^2}$
   $D_{y_C}=[-2,2] \cap ( [-3,3] + \sqrt{[16,16] - {( [6,7] - [2,3] )}^2})$
   $D_{y_C}=[-2,2] \cap [-3-\sqrt{7},3+\sqrt{7}]$
   $D_{y_C}=[-2,2]$
   donc $Q$= {$<C_2,y_D>$, $<C_1,y_C>$, $<C_3,y_D>$, $<C_3,x_D>$, $<C_1,x_C>$, $<C_2,x_C>$}.
4. $<C_2,y_D>$ : $y_D = y_C \pm \sqrt{16 - {(x_C-x_D)}^2}$.
   Projection des domaines $D_{y_D}$ = $D_{y_D} \cap ( D_{y_C} + \sqrt{[16,16] - {(D_{x_C} - D_{x_D})}^2}$
   $D_{y_D}=[-3,3] \cap ( [-2,2] + \sqrt{[16,16] - {( [6,7] - [2,3] )}^2})$
   $D_{y_D}=[-3,3] \cap [-2-\sqrt{7},2+\sqrt{7}]$
   $D_{y_D}=[-3,3]$ donc $Q$= { $<C_1,y_C>$, $<C_3,y_D>$, $<C_3,x_D>$, $<C_1,x_C>$, $<C_2,x_C>$ }.
5. $<C_1,y_C>$ : $y_C = \pm \sqrt{4 - {(x_C - 8)}^2}$.
   Projection des domaines $D_{y_C}$ = $D_{y_C} \cap ( \sqrt{[4,4] - {(D_{x_C} - [8,8])}^2} )$
   $D_{y_D} = [-2,2] \cap ( \sqrt{ [4,4] - {([6,7]-[8,8])}^2} )$ $D_{y_D} = [-2,2] \cap [-\sqrt{3},\sqrt{3}]$
   $D_{y_D} = [-\sqrt{3},\sqrt{3}]$
   donc $Q$= { $<C_3,y_D>$, $<C_3,x_D>$, $<C_1,x_C>$, $<C_2,x_C>$, $<C_2,x_D>$, $<C_2,y_D>$}.
6. $<C_3,y_D>$ : $y_D = \pm \sqrt{9 - {x_D}^2}$.
   Projection des domaines $D_{y_D}$ = $D_{y_D} \cap ( \sqrt{[9,9] - {D_{x_D}}^2} )$
   $D_{y_C} = [-3,3] \cap ( \sqrt{ [9,9] - [2,3]^2 } )$
   $D_{y_C} = [-3,3] \cap [-\sqrt{5},\sqrt{5}]$
   $D_{y_C} = [-\sqrt{5},\sqrt{5}]$ donc $Q$ = { $<C_3,x_D>$, $<C_1,x_C>$, $<C_2,x_C>$, $<C_2,x_D>$, $<C_2,y_D>$, $<C_2,y_C>$ }.

$\vdots$

Toutes les projections pour l'ensemble des couples de $Q$ ne modifieront plus les domaines des variables. L'instance 2B-consistante équivalente est donc :

$A(0,0)$, $B(8,0)$, $C(x_C,y_C)$, $D(x_D,y_D)$
$AB=8$, $AD=3$, $BC=2$, $CD=4$
$D_{x_C}=[6,7]$, $D_{y_C} = [-\sqrt{5},\sqrt{5}]$
$D_{x_D}=[2,3]$, $D_{y_D} = [-\sqrt{3},\sqrt{3}]$