5.408. two_orth_are_in_contact

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Roach84], used for defining πš˜πš›πšπš‘πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš.

Constraint

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

Type
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš˜πš›πš’-πšπšŸπšŠπš›,πšœπš’πš£-πšπšŸπšŠπš›,πšŽπš—πš-πšπšŸπšŠπš›)
Arguments
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄
Restrictions
|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄|>0
πš›πšŽπššπšžπš’πš›πšŽ_𝚊𝚝_πš•πšŽπšŠπšœπš(2,π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄,[πš˜πš›πš’,πšœπš’πš£,πšŽπš—πš])
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πšœπš’πš£>0
π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πš˜πš›πš’β‰€π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄.πšŽπš—πš
|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1|=|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2|
πš˜πš›πšπš‘_πš•πš’πš—πš”_πš˜πš›πš’_πšœπš’πš£_πšŽπš—πš(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1)
πš˜πš›πšπš‘_πš•πš’πš—πš”_πš˜πš›πš’_πšœπš’πš£_πšŽπš—πš(π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2)
Purpose

Enforce the following conditions on two orthotopes O 1 and O 2 :

  • For all dimensions i, except one dimension, the projections of O 1 and O 2 onto i have a non-empty intersection.

  • For all dimensions i, the distance between the projections of O 1 and O 2 onto i is equal to 0.

Example
πš˜πš›πš’-1 πšœπš’πš£-3 πšŽπš—πš-4,πš˜πš›πš’-5 πšœπš’πš£-2 πšŽπš—πš-7,πš˜πš›πš’-3 πšœπš’πš£-2 πšŽπš—πš-5,πš˜πš›πš’-2 πšœπš’πš£-3 πšŽπš—πš-5

FigureΒ 5.408.1 shows the two rectangles of the example. The 𝚝𝚠𝚘_πš˜πš›πšπš‘_πšŠπš›πšŽ_πš’πš—_πšŒπš˜πš—πšπšŠπšŒπš constraint holds since the two rectangles are in contact: the contact is depicted by a pink line-segment.

Figure 5.408.1. The two rectangles that are in contact of the Example slot where the contact is shown in pink
ctrs/two_orth_are_in_contact-1-tikz
Typical
|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄|>1
Symmetries
  • Arguments are permutable w.r.t. permutation (π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1,π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2).

  • Items of π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1 and π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2 are permutable (same permutation used).

Used in

πš˜πš›πšπš‘πšœ_πšŠπš›πšŽ_πšŒπš˜πš—πš—πšŽπšŒπšπšŽπš.

See also

implies: 𝚝𝚠𝚘_πš˜πš›πšπš‘_𝚍𝚘_πš—πš˜πš_πš˜πšŸπšŽπš›πš•πšŠπš™.

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.

geometry: geometrical constraint, touch, contact, non-overlapping, orthotope.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
β€’ πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1.πšŽπš—πš>πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ2.πš˜πš›πš’
β€’ πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ2.πšŽπš—πš>πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1.πš˜πš›πš’
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1|-1

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πš–πšŠπš‘0,πš–πšŠπš‘(πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1.πš˜πš›πš’,πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ2.πš˜πš›πš’)-πš–πš’πš—(πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ1.πšŽπš—πš,πš˜πš›πšπš‘πš˜πšπš˜πš™πšŽ2.πšŽπš—πš)=0
Graph property(ies)
𝐍𝐀𝐑𝐂=|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1|

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.408.2 respectively show the initial and final graph associated with the first graph constraint of 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 onto dimension 1 of the two rectangles of the example overlap.

Figure 5.408.2. Initial and final graph of the 𝚝𝚠𝚘_πš˜πš›πšπš‘_πšŠπš›πšŽ_πš’πš—_πšŒπš˜πš—πšπšŠπšŒπš constraint
ctrs/two_orth_are_in_contactActrs/two_orth_are_in_contactB
(a) (b)
Signature

Consider the second graph constraint. Since we use the arc generator π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡(=) on the collections π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1 and π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2, and because of the restriction |π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1|=|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄2|, the maximum number of arcs of the corresponding final graph is equal to |π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1|. Therefore we can rewrite the graph property 𝐍𝐀𝐑𝐂=|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1| to 𝐍𝐀𝐑𝐂β‰₯|π™Ύπšπšƒπ™·π™Ύπšƒπ™Ύπ™Ώπ™΄1| and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.

Automaton

FigureΒ 5.408.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 signature variable S i , which takes its value in {0,1,2}, as well as the following signature constraint:

((πš‚π™Έπš‰1 i >0)∧(πš‚π™Έπš‰2 i >0)∧(𝙴𝙽𝙳1 i >π™Ύπšπ™Έ2 i )∧(𝙴𝙽𝙳2 i >π™Ύπšπ™Έ1 i ))⇔S i =0

((πš‚π™Έπš‰1 i >0)∧(πš‚π™Έπš‰2 i >0)∧(𝙴𝙽𝙳1 i =π™Ύπšπ™Έ2 i βˆ¨π™΄π™½π™³2 i =π™Ύπšπ™Έ1 i ))⇔S i =1.

Figure 5.408.3. Automaton of the 𝚝𝚠𝚘_πš˜πš›πšπš‘_πšŠπš›πšŽ_πš’πš—_πšŒπš˜πš—πšπšŠπšŒπš constraint
ctrs/two_orth_are_in_contact-2-tikz
Figure 5.408.4. Hypergraph of the reformulation corresponding to the automaton of the 𝚝𝚠𝚘_πš˜πš›πšπš‘_πšŠπš›πšŽ_πš’πš—_πšŒπš˜πš—πšπšŠπšŒπš constraint
ctrs/two_orth_are_in_contact-3-tikz