National Center for Geographic Information and Analysis

In several applications, there is the need to reason about spatial relations using multiple local frames of reference organized in aggregation hierarchies. In this paper we deal with direction relations, a special class of spatial relations that describe order in space (e.g., north, northeast). We assume a spatial database of points and regions. Points belong to regions, which may be parts of larger regions and so on. The direction relations between points in the same region are explicitly represented. Inference mechanisms are applied to extract the relation between points in different regions and detect inconsistencies. We study two complementary types of inference. The first one derives the relation between two points that exist in different regions through chains of common points using path consistency. The second type of inference uses the relation between ancestor regions to infer the relation between the points. The paper describes algorithms for both types of inference and discusses their computational complexity.