### 3.7.57. Constructive disjunction

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 $\mathrm{𝚝𝚠𝚘}_\mathrm{𝚘𝚛𝚝𝚑}_\mathrm{𝚍𝚘}_\mathrm{𝚗𝚘𝚝}_\mathrm{𝚘𝚟𝚎𝚛𝚕𝚊𝚙}$ 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\le {X}_{1}$${X}_{1}+3\le {X}_{2}$${Y}_{2}+5\le {Y}_{1}$${Y}_{1}+2\le {Y}_{2}$
$\left[2,4\right]+2\le \left[3,5\right]$$\left[3,5\right]+3\le \left[2,4\right]$$\left[3,4\right]+5\le \left[6,7\right]$$\left[6,7\right]+2\le \left[3,4\right]$
$\left[2,\mathbf{3}\right]+2\le \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}:\varnothing$${Y}_{1}:\left\{6,7\right\}$${Y}_{1}:\left\{6,7\right\}$${Y}_{1}:\left\{6,7\right\}$
${Y}_{2}:\varnothing$${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}$