Qualitative spatial reasoning with topological information (Q1600087)

In this work the author investigates the adequate formalism for representing spatial knowedge based on the qualitative approach, i.e. spatial knowledge is represented by specifying qualitative relationships. The goal of research is to develop powerful representation formalisms which cover many aspects of space, which are provided with formal semantics, and which allow for efficient reasoning. The author presents as the basis for reaching this goal the topology of space because topological relationships are invariant with respect to continuous transformations of the underlying space. The Region Connection Calculus (RCC) is probably the best known approach to qualitative spatial representation und reasoning. RCC is a fully axiomatized first-order theory for representing topological relationships between spatial entities. The author presents empirical investigations of the cognitive adequacy of RCC and analyzes the computational properties of reasoning over RCC. He proves NP-hardness of the consistency problem of RCC-8, identifies a large maximal tractable subset of RCC-8 and shows that enforcing path-consistency is sufficient over relations of this set. The author proposes a general method for proving tractability of reasoning over systems of binary relations. Representational properties of RCC-8 are discussed.