A Boundary-Sensitive Approach to Qualitative Location

Abstract

Reasoning about the location of regions in 2-dimensional space is necessarily based on finite approximations to such regions. These finite approximations are often derived by describing how a region (the figure) relates to a frame of reference (the ground). The frame of reference generally consists of regions, or cells, forming a partition of the space under consideration. This paper presents a new approach to describing figure-ground relationships which is able to take account of how the figure relates to boundaries between cells as well as to their interiors. We also provide a general theory of how approximations to regions lead to approximations to operations on regions. This theory is applied to the case of our boundary-sensitive model of location. The paper concludes by indicating how interpreting boundaries in a more general sense should lead to a theory dealing with generalized partitions in which the cells may overlap. The applications of the theory developed here will include qualitative spatial reasoning, and should have practical relevance to geographical information systems.