5.343. two_orth_do_not_overlap

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Used for defining πšπš’πšπšπš—.

Constraint

𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1,π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2)

Type
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’-πšπšŸπšŠπš›,πšœπš’πš£-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Arguments
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄
Restrictions
|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄|>0
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄,[πš˜πš›πš’,πšœπš’πš£,πšŽπš—πš])
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πšœπš’πš£β‰₯0
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πš˜πš›πš’β‰€π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πšŽπš—πš
|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄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
πš˜πš›πš’-2 πšœπš’πš£-2 πšŽπš—πš-4,πš˜πš›πš’-1 πšœπš’πš£-3 πšŽπš—πš-4,πš˜πš›πš’-4 πšœπš’πš£-4 πšŽπš—πš-8,πš˜πš›πš’-3 πšœπš’πš£-3 πšŽπš—πš-6

FigureΒ 5.343.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.343.1. The two rectangles of the example
ctrs/two_orth_do_not_overlap1
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 β‰₯0.

  • π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2.πšœπš’πš£ can be decreased to any value β‰₯0.

Used in

πšπš’πšπšπš—.

See also

implied by: 𝚝𝚠𝚘_πš˜πš›πšπš‘_πšŠπš›πšŽ_πš’πš—_πšŒπš˜πš—πšπšŠπšŒπš.

Keywords

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

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency, constructive disjunction.

final graph structure: bipartite, no loop.

geometry: geometrical constraint, non-overlapping, orthotope.

Arc input(s)

π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1 π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2

Arc generator
π‘†π‘Œπ‘€π‘€πΈπ‘‡π‘…πΌπΆ_π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡(=)β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1,πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ2)

Arc arity
Arc constraint(s)
πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1.πšŽπš—πšβ‰€πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ2.πš˜πš›πš’βˆ¨πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1.πšœπš’πš£=0
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯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.343.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.343.2. Initial and final graph of the 𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™ constraint
ctrs/two_orth_do_not_overlapActrs/two_orth_do_not_overlapB
(a) (b)
Automaton

FigureΒ 5.343.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 th item of the π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1 collection. Let π™Ύπšπ™Έ2 i , πš‚π™Έπš‰2 i and 𝙴𝙽𝙳2 i respectively be the πš˜πš›πš’, the πšœπš’πš£ and the πšŽπš—πš attributes of the i th 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 πš‚ i as well as the following signature constraint: ((πš‚π™Έπš‰1 i >0)∧(πš‚π™Έπš‰2 i >0)∧(𝙴𝙽𝙳1 i >π™Ύπšπ™Έ2 i )∧(𝙴𝙽𝙳2 i >π™Ύπšπ™Έ1 i ))β‡”πš‚ i .

Figure 5.343.3. Automaton of the 𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™ constraint
ctrs/two_orth_do_not_overlap2
Figure 5.343.4. Hypergraph of the reformulation corresponding to the automaton of the 𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™ constraint
ctrs/two_orth_do_not_overlap3