On the representation of partial spatial information in knowledge bases

A fundamental requirement of advanced spatial applications is the capacity to deal with partial spatial information and multiple levels of granularity. This thesis studies the problem of representing and reasoning with partial spatial information in the context of knowledge bases. The thesis proposes a representation which views space as a totality of objects surrounded by a haze area and interrelated in terms of qualitative spatial relations. The most elementary object type in this representation, is the haze point. This is a non-zero sized object that is associated with an area of haze such that the point in question may be located anywhere inside it. Haze points are related in terms of an indistinguishability (called haze) or an order relation. The notion of haze can help us model situations where information is imprecise; the size of the haze area accounts for the degree of precision.;In the course of our study we present a formal axiomatization of the first-order theory of one-dimensional haze point space and develop several extensions of the theory for high dimensional space. We then define a set of topological and directional binary spatial relations in terms of the haze and order primitive relations and formalize spatial inferencing in a setting of varying degree of precision, as a constraint reasoning problem. Our reasoning algorithms make use of a data structure called haze-order graph which allows trading space for efficiency. Experimental results illustrate the efficiency of the proposed algorithms. Finally, we use these results in the development of a spatial data model which facilitates the representation of and reasoning with various forms of qualitatively and quantitatively incomplete spatial information, including indeterminate objects, multiple scales and granularity.