Information Technology Reference
In-Depth Information
has a solution, that is, to establish whether or not there exists an assignment of domain
values to variables that satisfies all constraints (
consistency checking
).
Cardinal relations are directional relations that allow one to specify how spatial ob-
jects are placed relative to each other either by making use of a fixed reference system,
e.g., to say that an object is to the “north” or “southwest” of another one in a geographic
space, or, alternatively, by exploiting directions as “above” or “below and left” in a lo-
cal space. The most expressive formalism with cardinal relations between plane regions
is the
Cardinal Direction calculus
(
CD-calculus
for short) [10,14,22]. The consistency
problem for the CD-calculus is NP-complete; moreover, in [12], it has been shown that
there exists no tractable fragment of it containing all basic constraints. Such a restriction
is a serious limitation when we have to deal with incomplete or indefinite information
in spatial applications.
A restricted version of the CD-calculus, called
Rectangular Cardinal Direction cal-
culus
(
RCD-calculus
), has been introduced in [19,18], where cardinal relations are de-
fined only between rectangles whose sides are parallel to the axes of the Euclidean
plane. Rectangles of this type (aka
boxes
) can be seen as
minimum bounding rectangles
(MBRs)
that enclose plane regions (the actual spatial objects). On the one hand, ap-
proximating regions by rectangles implies a loss of accuracy in the representation of the
relative direction between regions; on the other hand, reasoning tasks become more effi-
cient. The RCD-calculus has a strong connection with the
Rectangle Algebra
(RA) [2],
which can be viewed as a bidimensional extension of
Interval Algebra
(IA), the well-
known temporal formalism for dealing with qualitative binary relations between time
intervals [1]. A tractable fragment of the RCD-calculus, called
convex RCD-calculus
,
has been identified in [18]. It includes all basic relations and a large number of disjunc-
tive relations, making it possible to represent and reason about indefinite information
efficiently.
In this paper, we extend the convex RCD-calculus with metric constraints. Metric
constraints between points over a dense linear order have been dealt with by the Tem-
poral Constraint Satisfaction Problem formalism (TCSP) [7]. In such a formalism, one
can restrict the admissible values for the distance between a pair of points to a finite set
of ranges. If each constraint consists of one range only, we get a tractable fragment of
TCSP, called Simple Temporal Problem formalism (STP). In the following, we propose
a metric extension to the convex RCD-calculus that allows one to represent available
knowledge on directional relations between rectangles and to derive additional infor-
mation about them, as well as to deal with metric constraints on the height/width of a
rectangle or on the vertical/horizontal distance between rectangles. We will show that
the resulting formalism is expressive enough to capture various scenarios of practical
interest and still computationally affordable.
The rest of the paper is organized as follows. In Section 2, we provide background
knowledge on qualitative calculi and we shortly recall Interval Algebra and Rectangle
Algebra. In Section 3, we introduce the RCD-calculus and its convex fragment. In Sec-
tion 4, we extend the convex RCD-calculus with metric features, and we devise a sound
and complete polynomial algorithm for consistency checking. In Section 5, we apply
the proposed formalism to a case study in the domain of web-document layout design.
Conclusions provide an assessment of the work and outline future research directions.
