Global Constraint Catalog: Ctwo_orth_do_not

5.410. two_orth_do_not_overlap

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Used for defining $𝚍𝚒𝚏𝚏𝚗$ .

Constraint

$𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙 (𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1, 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2)$

Type

𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴

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

Arguments

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$	$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴$
$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$	$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴$

Restrictions

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

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

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

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

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

| 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 | = | 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2 |

𝚘𝚛𝚝𝚑_𝚕𝚒𝚗𝚔_𝚘𝚛𝚒_𝚜𝚒𝚣_𝚎𝚗𝚍

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

𝚘𝚛𝚝𝚑_𝚕𝚒𝚗𝚔_𝚘𝚛𝚒_𝚜𝚒𝚣_𝚎𝚗𝚍

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

Purpose

For two orthotopes $O_{1}$ and $O_{2}$ enforce that there exists at least one dimension $i$ such that the projections on $i$ of $O_{1}$ and $O_{2}$ do not overlap.

Example

(\begin{matrix} 〈𝚘𝚛𝚒 - 2 𝚜𝚒𝚣 - 2 𝚎𝚗𝚍 - 4, 𝚘𝚛𝚒 - 1 𝚜𝚒𝚣 - 3 𝚎𝚗𝚍 - 4〉, \\ 〈𝚘𝚛𝚒 - 4 𝚜𝚒𝚣 - 4 𝚎𝚗𝚍 - 8, 𝚘𝚛𝚒 - 3 𝚜𝚒𝚣 - 3 𝚎𝚗𝚍 - 6〉 \end{matrix})

Figure 5.410.1 represents the respective position of the two rectangles of the example. The coordinates of the leftmost lowest corner of each rectangle are stressed in bold. The $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint holds since the two rectangles do not overlap.

Figure 5.410.1. The two non overlapping rectangles of the Example slot

Typical

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

Symmetries

Arguments are permutable w.r.t. permutation $(𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1, 𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2)$ .
Items of $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ and $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$ are permutable (same permutation used).
$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1 . 𝚜𝚒𝚣$ can be decreased to any value $\geq 0$ .
$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2 . 𝚜𝚒𝚣$ can be decreased to any value $\geq 0$ .

Used in

$𝚍𝚒𝚏𝚏𝚗$ .

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: logic.

filtering: arc-consistency, constructive disjunction.

final graph structure: bipartite, no loop.

geometry: geometrical constraint, non-overlapping, orthotope.

Arc input(s)

$𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$

Arc generator

𝑆𝑌𝑀𝑀𝐸𝑇𝑅𝐼𝐶_𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1 . 𝚎𝚗𝚍 \leq 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 2 . 𝚘𝚛𝚒 \lor 𝚘𝚛𝚝𝚑𝚘𝚝𝚘𝚙𝚎 1 . 𝚜𝚒𝚣 = 0

Graph property(ies)

𝐍𝐀𝐑𝐂

\geq 1

Graph class

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

We build an initial graph where each arc corresponds to the fact that, either the projection of an orthotope on a given dimension is empty, either it is located before the projection in the same dimension of the other orthotope. Finally we ask that at least one arc constraint remains in the final graph.

Parts (A) and (B) of Figure 5.410.2 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the unique arc of the final graph is stressed in bold. It corresponds to the fact that the projection in dimension 1 of the first orthotope is located before the projection in dimension 1 of the second orthotope. Therefore the two orthotopes do not overlap.

Figure 5.410.2. Initial and final graph of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint


(a)	(b)

Automaton: Figure 5.410.3 depicts the automaton associated with the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint. Let $𝙾𝚁𝙸 1_{i}$ , $𝚂𝙸𝚉 1_{i}$ and $𝙴𝙽𝙳 1_{i}$ respectively be the $𝚘𝚛𝚒$ , the $𝚜𝚒𝚣$ and the $𝚎𝚗𝚍$ attributes of the $i^{t h}$ item of the $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 1$ collection. Let $𝙾𝚁𝙸 2_{i}$ , $𝚂𝙸𝚉 2_{i}$ and $𝙴𝙽𝙳 2_{i}$ respectively be the $𝚘𝚛𝚒$ , the $𝚜𝚒𝚣$ and the $𝚎𝚗𝚍$ attributes of the $i^{t h}$ item of the $𝙾𝚁𝚃𝙷𝙾𝚃𝙾𝙿𝙴 2$ collection. To each sextuple $(𝙾𝚁𝙸 1_{i}, 𝚂𝙸𝚉 1_{i}, 𝙴𝙽𝙳 1_{i}, 𝙾𝚁𝙸 2_{i}, 𝚂𝙸𝚉 2_{i}, 𝙴𝙽𝙳 2_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $((𝚂𝙸𝚉 1_{i} > 0) \land (𝚂𝙸𝚉 2_{i} > 0) \land (𝙴𝙽𝙳 1_{i} > 𝙾𝚁𝙸 2_{i}) \land (𝙴𝙽𝙳 2_{i} > 𝙾𝚁𝙸 1_{i})) \Leftrightarrow S_{i}$ .

Figure 5.410.3. Automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Figure 5.410.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.410. two_orth_do_not_overlap

Figure 5.410.1. The two non overlapping rectangles of the Example slot

Figure 5.410.2. Initial and final graph of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Figure 5.410.3. Automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Figure 5.410.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.410. two_orth_do_not_overlap

Figure 5.410.1. The two non overlapping rectangles of the Example slot

Figure 5.410.2. Initial and final graph of the 𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙 constraint

Figure 5.410.3. Automaton of the 𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙 constraint

Figure 5.410.4. Hypergraph of the reformulation corresponding to the automaton of the 𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙 constraint

Figure 5.410.2. Initial and final graph of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Figure 5.410.3. Automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint

Figure 5.410.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint