Interesting Problems for Cardinal Direction Relations: Composition and Consistency

Speaker: Spiros Skiadopoulos

Abstract

In this presentation, we discuss the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Initially, we formally define the relations that can be expressed in the above model. Then, we consider two interesting problems for cardinal direction relations: composition and consistency. For the composition operator, we consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We present the first algorithm for this task and prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in n5 time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss extensions of the basic cardinal direction relations model and outline algorithms for the composition and the consistency checking problem of these extensions.