### 3.7.57. Constructive disjunction

• $\mathrm{\pi \pi \pi \pi }$,

• .

A constraint for which a filtering algorithm uses constructive disjunction. Constructive disjunctionΒ [VanHentenryckSaraswatDeville95], [WurtzMuller96] is a technique for handling in an active way a set of disjunctive constraints. It consists to try out each alternative of a disjunction and then to remove values that were pruned in all alternatives. TableΒ 3.7.12 illustrates this technique in the context of a non -overlapping constraint between two rectangles (i.e.,Β a special case of the constraint). The first rectangle ${R}_{1}$ has a width of 3 and a height of 2, while the second rectangle ${R}_{2}$ has a width of 2 and a height of 5. The coordinates $\left({x}_{1},{y}_{1}\right)$ of the lower lefmost corner of ${R}_{1}$ have to be respectively located within intervals $\left[3,5\right]$ and $\left[6,7\right]$. Similarly the coordinates $\left({x}_{2},{y}_{2}\right)$ of the lower lefmost corner of ${R}_{2}$ have to be located within $\left[2,4\right]$ and $\left[3,4\right]$.

##### Table 3.7.12. Illustrating constructive disjunction in the context of a non -overlapping constraint between two rectangles.
Hypothesis regarding the respective position of ${R}_{1}$ and ${R}_{2}$
${R}_{2}$ before ${R}_{1}$:${R}_{2}$ after ${R}_{1}$:${R}_{2}$ below ${R}_{1}$:${R}_{2}$ on top of ${R}_{1}$:
${X}_{2}+2\beta €{X}_{1}$${X}_{1}+3\beta €{X}_{2}$${Y}_{2}+5\beta €{Y}_{1}$${Y}_{1}+2\beta €{Y}_{2}$
$\left[2,4\right]+2\beta €\left[3,5\right]$$\left[3,5\right]+3\beta €\left[2,4\right]$$\left[3,4\right]+5\beta €\left[6,7\right]$$\left[6,7\right]+2\beta €\left[3,4\right]$
$\left[2,\mathbf{3}\right]+2\beta €\left[\mathbf{4},5\right]$contradictioncontradictioncontradiction
Removed values from each variable according to each hypothesis
${X}_{1}:\left\{3\right\}$${X}_{1}:\left\{3,4,5\right\}$${X}_{1}:\left\{3,4,5\right\}$${X}_{1}:\left\{3,4,5\right\}$
${X}_{2}:\left\{4\right\}$${X}_{2}:\left\{2,3,4\right\}$${X}_{2}:\left\{2,3,4\right\}$${X}_{2}:\left\{2,3,4\right\}$
${Y}_{1}:\mathrm{\beta  }$${Y}_{1}:\left\{6,7\right\}$${Y}_{1}:\left\{6,7\right\}$${Y}_{1}:\left\{6,7\right\}$
${Y}_{2}:\mathrm{\beta  }$${Y}_{2}:\left\{3,4\right\}$${Y}_{2}:\left\{3,4\right\}$${Y}_{2}:\left\{3,4\right\}$
Values finally removed: value 3 from ${X}_{1}$ and value 4 from ${X}_{2}$