Order in space: a general formalism for spatial reasoning

In this paper we propose a general approach for reasoning in space. The approach is composed of a set of two general constraints to govern the spatial relationships between objects in space, and two rules to propagate relationships between those objects. The approach is based on a novel representation of the topology of the space as a connected set of components using a structure called adjacency matrix which can capture the topology of objects of different complexity in any space dimension. The formalism is used to explain spatial compositions resulting in indefinite and definite relations and it is shown to be applicable to reasoning in the temporal domain. The main contribution of the formalism is that it provides means for constructing composition tables for objects with arbitrary complexity in any space dimension. A new composition table between spatial objects of different types is presented. A major advantage of the method is that reasoning between objects of any complexity can be achieved in a defined limited number of steps. Hence, the incorporation of spatial reasoning mechanisms in spatial information systems becomes possible