1 Introduction
It is widely accepted that spatial reasoning plays a central role in artificial intelligence, for it has a wide variety of potential applications e.g. in robotics, geographical information systems, medical analysis and diagnosis. As for other qualitative reasoning formalisms (e.g., temporal reasoning), spatial reasoning can be viewed under three different, somehow complementary, points of view. We may distinguish between the algebraic level, that is, purely existential theories formulated as constraint satisfaction systems over jointly exclusive and mutually disjoint set of topological, directional, or combined relations; the first-order level, that is, first-order theories of topological, directional, or combined relations; and the modal logic level, where a (usually propositional) modal language is interpreted over opportune Kripke structures representing space. For a comprehensive survey on the various formalisms (topological, directional, and combined constraint systems and relations) see [8].