
| Notation                 | Meaning                                                                          |    |    |    |
|--------------------------|----------------------------------------------------------------------------------|----|----|----|
| a, b                     | regions                                                                          |    |    |    |
| Ix(a), Iy(a)             | the x- and y-projections of a                                                    |    |    |    |
| M(a)                     | the minimum bounding rectangle (mbr) of a                                        |    |    |    |
| α, β                     | basic IA relations                                                               |    |    |    |
| α ⊗ β                    | a basic RA relation                                                              |    |    |    |
| δ1 :· · ·: δk            | a basic CDC relation                                                             |    |    |    |
| u, v, w                  | spatial variables                                                                |    |    |    |
| k                        | the right-side parallel relation with gap (parallel relation for short)          |    |    |    |
| p                        | the upper left corner (ULC) relation                                             |    |    |    |
| Nα⊗β                     | the basic CDC network that entails the RA relation α ⊗ β                         |    |    |    |
| Nk                       | the basic CDC network that entails k                                             |    |    |    |
| Np                       | the basic CDC network that entails p                                             |    |    |    |
| φ                        | a 3-SAT instance                                                                 |    |    |    |
| p, pr, ps, pt            | propositional variables                                                          |    |    |    |
| ∗ , p∗ , p∗ p t          | propositional literals                                                           |    |    |    |
| r                        | s                                                                                |    |    |    |
| c, cj                    | propositional clauses                                                            |    |    |    |
| Np                       | the basic CDC network for propositional variable p                               |    |    |    |
| NV                       | the basic CDC network for all propositional variables in V                       |    |    |    |
| Nc                       | the basic CDC network for propositional clause c                                 |    |    |    |
| Nφ                       | the basic CDC network for 3-SAT instance φ                                       |    |    |    |
| fp, f¬p, f 0 p           | the frame spatial variables for propositional variable p                         |    |    |    |
| up, u¬p                  | the dual spatial variables for propositional variable p                          |    |    |    |
| vc                       | the spatial variable for propositional clause c                                  |    |    |    |
| w c , wc rs, wc st, wc 0 | the 'pier' spatial variables for propositional clause c                          |    |    |    |
| 0                        | ∗                                                                                | ∗  |    |    |
| u r                      | the spatial variable corresponding to p r c , u∗ , wc rs, u∗ , wc st, u∗ , wc 1} |    |    |    |
| Xc                       | the spatial variable set {w 0                                                    | r  | s  | t  |
| Table 1: Notations.      |                                                                                  |    |    |    |
