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.
Current research on qualitative spatial representation and reasoning mainly
focuses on one single aspect of space. In real world applications, however,
multiple spatial aspects are often involved simultaneously.
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.
Topological information are the most important kind of qualitative spatial
information. Current formalisms for the topological aspect of space focus on
the global relations between regions, while overlooking their internal
structure. Complex regions could be of multiple pieces and/or have holes and
islands to any finite level. We propose a layered graph model for representing
the internal structure of complex plane regions, where each node represents a
connected component of the interior or the exterior of a complex region.