This thesis is an in-depth study in the area of Qualitative Spatial Representation and Reasoning. The study is motivated by the potential advantages to be gained from the utilisation of qualitative representation and reasoning techniques in large spatial systems. Qualitative handling of spatial objects and relations has been an active research area in the past 10 to 15 years. The complexity of the issues to be considered has hampered the utilisation of research results in the current generation of spatial information systems and databases. Towards improving this situation, this thesis starts by identifying the main challenges facing the domain of QSRR, namely, the trade-off between expressiveness and efficiency and the trade-off between the completeness and soundness of the approaches. Towards facing the first challenge, a representation formalism is proposed for spatial objects of arbitrary complexity and for different types of spatial relationships between them. Based on the representation methodology, a reasoning formalism is developed to derive the composition of spatial relationships between those objects. The method have been validated by a simple prototype reasoning engine which derives the composition tables between different object types in the topological space. Further more, a study of the application of the methods in the spatio-temporal domain and in uncertain qualitative spaces is presented. The methodology used in this thesis guarantees completeness, in the sense that all relationships between the spatial objects considered are covered. It, however, does not guarantee soundness, in the sense of finding only the physically possible set of those relationships. Accordingly, a set of rules representing topological invariants are also identified which are shown to reduce the set of complete relations to the set of sound ones. The main contribution of this thesis is that it presents a step towards the realisation of the practical application of QSRR techniques in spatial information systems.
|Date of Award