Information Technology Reference
In-Depth Information
convex RCD-relations
. As we already pointed out, the convex subclasses of IA, PA, and
RA are tractable. By exploiting the connection between these subclasses and the convex
RCD-calculus, an
O
(
n
2
)
algorithm for consistency checking of convex RCD-networks
has been proposed in [18]. In particular, it benefits from the following result about RA,
stated in [2].
Theorem 3.
Let
N
be a convex RA-network.
N
is consistent if and only if its projec-
tions
π
x
(
N
)
and
π
y
(
N
)
are consistent.
4
Convex-Metric RCD-Calculus
In this section, we propose a tractable metric extension of the convex RCD-calculus,
called
convex-metric RCD-calculus
(
cmRCD-calculus
) to represent and to reason about
both qualitative cardinal constraints between rectangles and metric constraints on the
distance between the endpoints of their projections. The main tool we use to deal with
metric information in the cmRCD-calculus is STP. More precisely, we use STP to elab-
orate information on the endpoints of
MBR
projections onto the Cartesian axes.
Integrating the convex RCD-calculus with STP makes it possible to express both
directional constraints and metric constraints in a uniform framework. As an exam-
ple, the resulting formalism allows one to constrain the position of a rectangle in the
plane and to impose minimum and/or maximum values to the width/height of a given
rectangle, or on the vertical/horizontal distances between the sides of two rectangles.
Obviously, RCD-constraints and STP-constraints are not totally independent, that is,
RCD-constraints entail some metric constraints and vice versa.
Example 2.
Let
a
and
b
be two rectangles. We can use the metric constraint
0
≤
a
x
−
a
x
≤
7
to state that the maximum width of
a
is
7
and, similarly, we can ex-
ploit the metric constraint
2
a
y
to state that the minimum height of
a
is
2
(leaving the maximum height unbounded). We can also express distance constraints
between the boundaries of
a
and
b
. We can constrain the horizontal distance between
the right side of
a
and the left side of
b
to be at least
3
by means of the constraint
3
a
y
−
≤
a
x
, and the vertical distance between the upper side of
a
and the bottom
side of
b
to be greater than or equal to
0
by means of the constraint
0
b
x
−
≤
b
y
−
a
y
.
≤
The two constraints together entail the basic RCD constraint
a
b
. Finally, some
metric constraints can be entailed by RCD ones. For instance, the convex relation
a
{
SW
}
b
y
.
If we allow one to combine arbitrary RCD-constraints with metric constraints, then
checking the consistency of the resulting set of constraints turns out to be an NP-
complete problem (the consistency problem for RCD-networks is already NP-complete).
To preserve tractability, the cmRCD-calculus combines convex RCD-constraints with
STP-constraints. Constraint networks in the cmRCD-calculus (
cmRCD-networks
)are
defined as follows. Given a convex RCD-network
N
c
=(
V,C
)
, we denote the sets of
interval variables belonging to the projections
π
x
(
toRA
(
N
c
))
and
π
y
(
toRA
(
N
c
))
by
V
x
and
V
y
, respectively. Moreover, we denote by
P
(
V
x
)
and
P
(
V
y
)
the sets of point
variables representing the endpoints of the interval variables in
V
x
and
V
y
, respectively.
{
NW,N,NE,NW
:
N,NW
:
N
:
NE,N
:
NE
}
b
implies that
0
≤
a
y
−
