When considering only rectangles, the ULC relation is exactly the union of two basic rectangle relations, namely s ⊗ fi and its converse si ⊗ f, where s, f are basic relations in the IA, and si and fi are their converses (see Table 2 for the meanings of basic IA relations).

Write p for the ULC relation. The consistency decision problem over Bdir*∪{∗}* is, roughly speaking, equivalent to that over Bdir *∪ {∗*, p}. The NP-hardness of Bdir *∪ {∗*, p} is then not hard to imagine.

![0_image_0.png](0_image_0.png)

Such a technique for defining relations outside a qualitative calculus was also used in
[8] for generalizing the tractability of subclasses of the IA.

Our reduction does not require regions to be connected. Therefore, the above NPhardness result is also applicable to CDCd, a variant of the CDC which deals with cardinal direction relations between possibly disconnected plane regions [16, 10]. That is, the consistency decision problem of (possibly incomplete) basic CDCd networks is also an NP-hard problem. This suggests that the O(n 5) consistency checking algorithm proposed in [16] is incomplete.

The remainder of this paper proceeds as follows. Section 2 introduces the CDC and some basic notions used in this paper. Section 3 shows examples of relations outside the CDC that are definable in the CDC. The main result is proved in Section 4, which is followed by an analysis of the correctness of the O(n 5) algorithm in [16]. The last section concludes the paper.

Table 1 summarizes major and special notations used in this paper.

## 2. Cardinal Direction Calculus: Definitions And Basic Notations

In this section, we introduce definitions and basic notations of the cardinal direction calculus. We refer the readers to [10] for further discussions about this calculus.