# Reasoning About Cardinal Directions Between Extended Objects: The Hardness Result

Weiming Liu, Sanjiang Li∗
Centre for Quantum Computation and Intelligent Systems, Faculty of Engineering and Information Technology, University of Technology, Sydney, Australia

## Abstract

The cardinal direction calculus (CDC) proposed by Goyal and Egenhofer is a very expressive qualitative calculus for directional information of extended objects. Early work has shown that consistency checking of *complete* networks of basic CDC constraints is tractable while reasoning with the CDC in general is NP-hard. This paper shows, however, if allowing some constraints unspecified, then consistency checking of *possibly incomplete* networks of basic CDC constraints is already intractable. This draws a sharp boundary between the tractable and intractable subclasses of the CDC. The result is achieved by a reduction from the well-known 3-SAT problem.

Key words: Qualitative spatial reasoning, Cardinal direction calculus, NP-hardness, Consistency checking, Reduction

## 1. Introduction

Direction relations between extended spatial objects are important commonsense knowledge. Most existing direction relation models approximate a spatial object by a point (e.g. its centroid) or a box. This is certainly imprecise in real-world applications such as describing the directional information between two countries, say, Portugal and Spain [15].

Goyal and Egenhofer [5, 6] proposed the *direction relation matrix* (DRM) for representing direction relations between *connected* plane regions. The original description of the DRM lacks formality and does not consider limit cases. This problem was fixed in arXiv:1011.0233v2 [cs.AI] 4 Nov 2010