An entailed relation is not necessarily a CDC relation.

The polynomial reduction from 3-SAT will rely heavily on one particular entailed relation, namely, the upper left corner (ULC) relation. Before discussing the ULC relation, we first review basic notions of the Rectangle Algebra and give some simple examples of entailed relations.

The Rectangle Algebra (RA) [2] is a qualitative calculus previously defined on all rectangles sides of which are parallel to the x- and y-axes. Relations in the RA can be naturally extended to the set of all bounded regions. For two bounded regions *a, b*, the basic RA relation of a to b is written as α ⊗ β, where *α, β* are basic IA relations and Ix(a)αIx(b) and Iy(a)βIy(b). Table 2 summarizes notations and definitions of the basic IA relations. For each basic RA relation α ⊗ β, the following equation is clear.

(*a, b*) ∈ α ⊗ β ⇔ (M(a),M(b)) ∈ α ⊗ β. (9)

| Relation         | Symbol   | Converse   | Meaning              |
|------------------|----------|------------|----------------------|
| − < x+ < y− < y+ |          |            |                      |
| before           | p        | pi         | x − < x+ = y − < y+  |
| meets            | m        | mi         | x                    |
| overlaps         | o        | oi         | x − < y− < x+ < y+   |
| starts           | s        | si         | x − = y − < x+ < y+  |
| during           | d        | di         | y − < x− < x+ < y+   |
| finishes         | f        | fi         | y − < x− < x+ = y +  |
| equals           | eq       | eq         | x − = y − < x+ = y + |

Table 2: Basic IA relations and their converse, where x = [x
−, x+], y = [y
−, y+] are two intervals.

We next show that some extended basic RA relations can be defined in the CDC.

Example 1. A proper subset of the extended basic RA relation s⊗f can be entailed by the following basic CDC network

$${\mathcal{N}}_{\mathbf{s}\otimes\mathbf{f}}=\{u\;O\;v,v\;E\!:\!S E\!:\!S\!:\!O\;u\}.$$
Ns⊗f = {u O v, v E :SE :S :O u}. (10)
It is easy to see that if (*a, b*) satisfies Ns⊗f, then M(a) is contained in, and shares the upper left corner point with, M(b) (cf. Figure 3(a)). In terms of the RA language, we have (M(a),M(b)) ∈ s ⊗ f. We stress that (*a, b*) may be not a solution to Ns⊗f even if
(M(a),M(b)) ∈ s ⊗ f. This is because the CDC relation of b to a could be, for example, E :SE :S. But when only rectangles are considered, it is straightforward to see that s ⊗ f is exactly the relation entailed by Ns⊗f.

$\left(10\right)^{2}$