Global Constraint Catalog: Cdiffn

5.119. diffn_column

DESCRIPTION

LINKS

GRAPH

Origin

CHIP: option guillotine cut (column) of $𝚍𝚒𝚏𝚏𝚗$ .

Constraint

$𝚍𝚒𝚏𝚏𝚗_𝚌𝚘𝚕𝚞𝚖𝚗 (𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂, 𝙳𝙸𝙼)$

Type

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒 - 𝚍𝚟𝚊𝚛, 𝚜𝚒𝚣 - 𝚍𝚟𝚊𝚛, 𝚎𝚗𝚍 - 𝚍𝚟𝚊𝚛)

Arguments

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚝𝚑 - 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴)$
$𝙳𝙸𝙼$	$𝚒𝚗𝚝$

Restrictions

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎_𝚊𝚝_𝚕𝚎𝚊𝚜𝚝

(2, 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴, [𝚘𝚛𝚒, 𝚜𝚒𝚣, 𝚎𝚗𝚍])

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚜𝚒𝚣 \geq 0

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚘𝚛𝚒 \leq 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚎𝚗𝚍

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂, 𝚘𝚛𝚝𝚑)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂, 𝚘𝚛𝚝𝚑)

𝙳𝙸𝙼 > 0

𝙳𝙸𝙼 \leq | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 |

𝚍𝚒𝚏𝚏𝚗

(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂)

Purpose

Extension of the generalised multi-dimensional non-overlapping diffn constraint. Holds if, for each pair of orthotopes $(O_{1}, O_{2})$ the following conditions hold:

$O_{1}$ and $O_{2}$ do not overlap. Two orthotopes do not overlap if one of the orthotopes has zero size or if there exists at least one dimension where their projections do not overlap.
Let $P_{1}$ and $P_{2}$ respectively denote the projections of $O_{1}$ and $O_{2}$ onto dimension $𝙳𝙸𝙼$ . If $P_{1}$ and $P_{2}$ overlap then the size of their intersection is equal to the size of $O_{1}$ in dimension $𝙳𝙸𝙼$ , as well as to the size of $O_{2}$ in dimension $𝙳𝙸𝙼$ .

Example

(\begin{matrix} 〈\begin{matrix} 𝚘𝚛𝚝𝚑 - 〈𝚘𝚛𝚒 - 1 𝚜𝚒𝚣 - 3 𝚎𝚗𝚍 - 4, 𝚘𝚛𝚒 - 3 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 5〉, \\ 𝚘𝚛𝚝𝚑 - 〈\begin{matrix} 𝚘𝚛𝚒 - 9 & 𝚜𝚒𝚣 - 1 & 𝚎𝚗𝚍 - 10, \\ 𝚘𝚛𝚒 - 4 & 𝚜𝚒𝚣 - 3 & 𝚎𝚗𝚍 - 7 \end{matrix}〉, \\ 𝚘𝚛𝚝𝚑 - 〈𝚘𝚛𝚒 - 4 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 6, 𝚘𝚛𝚒 - 3 𝚜𝚒𝚣 - 4 𝚎𝚗𝚍 - 7〉, \\ 𝚘𝚛𝚝𝚑 - 〈𝚘𝚛𝚒 - 1 𝚜𝚒𝚣 - 3 𝚎𝚗𝚍 - 4, 𝚘𝚛𝚒 - 6 𝚜𝚒𝚣 - 1 𝚎𝚗𝚍 - 7〉, \\ 𝚘𝚛𝚝𝚑 - 〈𝚘𝚛𝚒 - 6 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 8, 𝚘𝚛𝚒 - 1 𝚜𝚒𝚣 - 4 𝚎𝚗𝚍 - 5〉, \\ 𝚘𝚛𝚝𝚑 - 〈\begin{matrix} 𝚘𝚛𝚒 - 10 & 𝚜𝚒𝚣 - 1 & 𝚎𝚗𝚍 - 11, \\ 𝚘𝚛𝚒 - 1 & 𝚜𝚒𝚣 - 1 & 𝚎𝚗𝚍 - 2 \end{matrix}〉, \\ 𝚘𝚛𝚝𝚑 - 〈\begin{matrix} 𝚘𝚛𝚒 - 9 & 𝚜𝚒𝚣 - 1 & 𝚎𝚗𝚍 - 10, \\ 𝚘𝚛𝚒 - 1 & 𝚜𝚒𝚣 - 1 & 𝚎𝚗𝚍 - 2 \end{matrix}〉, \\ 𝚘𝚛𝚝𝚑 - 〈𝚘𝚛𝚒 - 6 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 8, 𝚘𝚛𝚒 - 6 𝚜𝚒𝚣 - 1 𝚎𝚗𝚍 - 7〉 \end{matrix}〉, 1 \end{matrix})

Figure 5.119.1 represents the respective position of the eight rectangles of the example. The coordinates of the leftmost lowest corner of each rectangle are stressed in bold. The $𝚍𝚒𝚏𝚏𝚗_𝚌𝚘𝚕𝚞𝚖𝚗$ constraint holds since (1) the eight rectangles do not overlap and since (2) when their projection onto dimension $𝙳𝙸𝙼 = 1$ overlap the size of their intersection is equal to the size of the corresponding rectangles in dimension $𝙳𝙸𝙼 = 1$ .

Figure 5.119.1. Illustration of the Example slot: eight non-overlapping rectangles such that, for each pair of rectangles $R_{i}$ , $R_{j}$ $(1 \leq i < j \leq 8)$ , if the projections onto dimension 1 of rectangles $R_{i}$ and $R_{j}$ intersect then the size of their intersection is equal to the size of $R_{i}$ in dimension 1 and to the size of $R_{j}$ in dimension 1 (i.e. complete vertical strips along the border of any rectangle can be cut without crossing any rectangle)

Typical

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 | > 1

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 . 𝚜𝚒𝚣 > 0

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂 | > 1

Symmetries

Items of $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂$ are permutable.
One and the same constant can be added to the $𝚘𝚛𝚒$ and $𝚎𝚗𝚍$ attributes of all items of $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂 . 𝚘𝚛𝚝𝚑$ .

Arg. properties

Contractible wrt. $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂$ .

implies: $𝚍𝚒𝚏𝚏𝚗_𝚒𝚗𝚌𝚕𝚞𝚍𝚎$ .

used in graph description: $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚌𝚘𝚕𝚞𝚖𝚗$ .

Keywords

constraint type: decomposition.

geometry: geometrical constraint, positioning constraint, orthotope, guillotine cut.

Arc input(s)

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

(<) \mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎𝚜 1, 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎𝚜 2)

Arc arity

Arc constraint(s)

𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚌𝚘𝚕𝚞𝚖𝚗

(𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎𝚜 1 . 𝚘𝚛𝚝𝚑, 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎𝚜 2 . 𝚘𝚛𝚝𝚑, 𝙳𝙸𝙼)

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂 | * (| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴𝚂 | - 1) / 2

Graph model

Since showing all items produces too big graphs, parts (A) and (B) of Figure 5.119.2 respectively show the initial and final graph associated with the first three items of the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the arcs of the final graph are stressed in bold.

Figure 5.119.2. Initial and final graph of the $𝚍𝚒𝚏𝚏𝚗_𝚌𝚘𝚕𝚞𝚖𝚗$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.119. diffn_column

Figure 5.119.2. Initial and final graph of the 𝚍𝚒𝚏𝚏𝚗_𝚌𝚘𝚕𝚞𝚖𝚗 constraint

Figure 5.119.2. Initial and final graph of the $𝚍𝚒𝚏𝚏𝚗_𝚌𝚘𝚕𝚞𝚖𝚗$ constraint