Originating from Allen's Interval Algebra, composition-based reasoning has
been widely acknowledged as the most popular reasoning technique in qualitative
spatial and temporal reasoning. Given a qualitative calculus (i.e. a relation
model), the first thing we should do is to establish its composition table
(CT). In the past three decades, such work is usually done manually. This is
undesirable and error-prone, given that the calculus may contain tens or
hundreds of basic relations. Computing the correct CT has been identified by
Tony Cohn as a challenge for computer scientists in 1995.
Direction relations between extended spatial objects are important
commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model,
known as Cardinal Direction Calculus (CDC), for representing direction
relations between connected plane regions. CDC is perhaps the most expressive
qualitative calculus for directional information, and has attracted increasing
interest from areas such as artificial intelligence, geographical information
science, and image retrieval.