Information Technology Reference
In-Depth Information
Theorem 4.
Given a cmRCD-network
N
=(
N
c
,
S
x
,
S
y
)
, the algorithm
con
-
cmRCD
returns 'consistent' if and only if
N
is consistent.
Proof.
We basically follow the steps of the algorithm. By Theorem 2,
N
c
is consistent
if and only if
N
r
is consistent, and, by Theorem 3,
N
r
is consistent if and only if
N
x
and
N
y
are consistent (they can be checked independently). Next,
N
x
and
N
y
are consistent
if and only if
N
x
and
N
y
are consistent, since there is no loss in information in the
translations [24]. The consistency of
N
x
and
N
y
can be checked by computing the
corresponding STPs and by applying
PC
stp
. However, we cannot apply
PC
stp
directly
to the STPs
toSTP
(
N
x
)
and
toSTP
(
N
x
)
since the metric constraints of
S
x
and
S
y
must be taken into account. Hence, we compute
xSTP
=
intersect
(
toSTP
(
N
x
)
,S
x
)
and
ySTP
=
intersect
(
toSTP
(
N
x
)
,S
y
)
. If one of them returns an empty network,
then
N
is inconsistent. Otherwise, we independently apply
PC
stp
to
xSTP
and
ySTP
.
By Theorem 1, if one of the two applications of
PC
stp
returns an empty network, then
N
is inconsistent; otherwise, the path-consistent STPs
xSTP
min
and
ySTP
min
are
consistent (and minimal), and thus
N
is consistent.
Theorem 5.
The complexity of the algorithm
con
-
cmRCD
is
O
(
n
3
)
,where
n
is the
number of variables of the input network.
Proof.
The translation via
toRA
, the generation of a projection of a network, the trans-
formation of an IA-network into an RA-network via
toPA
, and the last two encodings
via
toSTP
require
O
(
n
2
)
steps, since there are
O
(
n
2
)
constraints and each constraint
can be translated in constant time. The function
toPA
introduces two variables for each
interval variable, so
xSTP
and
ySTP
have
O
(
n
)
variables each. Finally,
PC
stp
runs
in
O
(
n
3
)
time, so the overall complexity is
O
(
n
3
)
time (for further details about the
complexity of achieving path-consistency for combined networks see [16]).
Once we have computed the path-consistent STPs
xSTP
min
and
ySTP
min
with algo-
rithm
con
-
cmRCD
, we can build a
solution
to the cmRCD-network
N
by computing
a solution for the points in
xSTP
min
and
ySTP
min
, since the assignment for point
variables defines a consistent assignment for rectangle variables (see Example 1). To
this end, the
O
(
n
3
)
algorithm
STP
-
SOLUTION
, by Gerevini and Cristani [9], can be
used.
5
A Case Study for the cmRCD-Calculus
Given its distinctive features, the cmRCD-calculus is well-suited for all application
areas where minimal bounding rectangles can be successfully exploited. This is the
case, for instance, with spatial databases [10,21], information extraction from formatted
documents [8,20], and 2D-layout design [3,4,17]. We would also like to mention the
application of convex RCD-calculus (the qualitative fragment of cmRCD-calculus) to
the problem querying and extracting data from web documents reported in [20]. We
believe that, in view of its well-balanced combination of efficiency and expressiveness,
cmRCD-calculus can be naturally and successfully applied to this class of problems as
well.
