Redundancy checking is an important task in AI subfields such as knowledge representation and constraint solving. This paper considers redundant topological constraints, defined in the region connection calculus RCC8. We say a constraint in a set C of RCC8 constraints is redundant if it is entailed by the rest of C. A prime subnetwork of C is a subset of C which contains no redundant constraints and has the same solution set as C. It is natural to ask how to compute such a prime subnetwork, and when it is unique. While this problem is in general intractable, we show that, if S is a subalgebra of RCC8 in which weak composition distributes over nonempty intersections, then C has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from C. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal.

How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.

Increasing the expressiveness of qualitative spatial calculi is an essential step towards meeting the requirements of applications. This can be achieved by combining existing calculi in a way that we can express spatial information using relations from multiple calculi. The great challenge is to develop reasoning algorithms that are correct and complete when reasoning over the combined information. Previous work has mainly studied cases where the interaction between the combined calculi was small, or where one of the two calculi was very simple. In this paper we tackle the important combination of topological and directional information for extended spatial objects. We combine some of the best known calculi in qualitative spatial reasoning, the RCC8 algebra for representing topological information, and the Rectangle Algebra (RA) and the Cardinal Direction Calculus (CDC) for directional information. We consider two different interpretations of the RCC8 algebra, one uses a weak connectedness relation, the other uses a strong connectedness relation. In both interpretations, we show that reasoning with topological and directional information is decidable and remains in NP. Our computational complexity results unveil the significant differences between RA and CDC, and that between weak and strong RCC8 models. Take the combination of basic RCC8 and basic CDC constraints as an example: we show that the consistency problem is in P only when we use the strong RCC8 algebra and explicitly know the corresponding basic RA constraints.

Topological relations between spatial objects are the most important kind of qualitative spatial information. Dozens of relation models have been proposed in the past two decades. These models usually make a small number of distinctions and therefore can only cope with spatial information at a fixed granularity of spatial knowledge. In this paper, we propose a topological relation model in which the topological relation between two convex plane regions can be uniquely represented as a circular string over the alphabet {u; v; x; y}. A linear algorithm is given to compute the topological relation between two convex polygons. The infinite relation calculus could be used in hierarchical spatial reasoning as well as in qualitative shape description.