Information Technology Reference
In-Depth Information
Efficient Spatial Reasoning with Rectangular
Cardinal Relations and Metric Constraints
Angelo Montanari
1
, Isabel Navarrete
2
, Guido Sciavicco
2
, and Alberto Tonon
3
1
Department of Mathematics and Computer Science. University of Udine, Italy
2
Department of Information Engineering. University of Murcia, Spain
3
eXascale Infolab. University of Fribourg, Switzerland
angelo.montanari@uniud.it,
{
inava,guido
}
@um.es,
alberto.tonon@unifr.ch
Abstract.
In many real-world applications of knowledge representation and rea-
soning formalisms, one needs to cope with a number of spatial aspects in an
integrated and efficient way. In this paper, we focus our attention on the so-called
Rectangular Cardinal Direction calculus for qualitative spatial reasoning on car-
dinal relations between rectangles whose sides are parallel to the axes of a fixed
reference system. We show how to extend its convex tractable fragment with
metric constraints preserving tractability. The resulting formalism makes it pos-
sible to efficiently reason about spatial knowledge specified by one qualitative
constraint network and two metric networks (one for each spatial dimension).
In particular, it allows one to represent definite or imprecise knowledge on di-
rectional relations between rectangles and to derive additional information about
them, as well as to deal with metric constraints on the height/width of a rectangle
or on the vertical/horizontal distance between the sides of two rectangles. We be-
lieve that the formalism features a good combination of simplicity, efficiency, and
expressive power, making it adequate for spatial applications like, for instance,
web-document query processing and automatic layout generation.
Keywords:
Qualitative spatial reasoning, Quantitative spatial reasoning, Cardi-
nal direction relations, Constraint satisfaction problems.
1
Introduction
Qualitative spatial representation and reasoning play an important role in various ar-
eas of computer science such as, for instance, geographic information systems, spatial
databases, document analysis, layout design, and image retrieval. Different aspects of
space, such as direction, topology, size, and distance, which must be dealt with in a
coherent way in many real-world applications, have been modeled by different formal
systems (see [5] for a survey). For practical reasons, a bidimensional space is com-
monly assumed, and spatial entities are represented by points, boxes, or polygons with
a variety of shapes, depending on the required level of detail.
Information about spatial configurations is usually specified by constraint networks
describing the allowed binary relations between pairs of spatial variables. The main
problem in qualitative spatial reasoning is to decide whether or not a given network
