Information Technology Reference
In-Depth Information
solution to the network, that is, a possible layout of the user home page, is given in
Figure 5. It is worth pointing out that the picture shows the minimum feasible values
for point variables, and thus it immediately follows that the minimum dimension of
h
is
1024
×
1974
px.
6
Conclusions
In this paper, we have proposed a quite expressive, but tractable, metric extension of
RCD-calculus, that integrates convex RCD-constraints and STP-constraints. The result-
ing cmRCD-calculus allows one to constrain the position of a rectangle in the plane, its
width/height, and the vertical/horizontal distance between the sides of two rectangles,
as well as to represent cardinal relations between rectangles. We have developed an
O
(
n
3
)
consistency-checking algorithm for such a calculus, and we have shown how a
spatial realization of a
cmRCD-network
can be built.
As for future work, we plan to extend the cmRCD-calculus with topological relations
to improve its expressiveness (similar results can be found in [11,13]). Moreover, since
the problem of identifying maximal tractable subsets of RCD is still open, it makes
sense to search for tractable classes strictly including the convex fragment. Finally, we
are interested in developing heuristics and algorithms to check consistency and to find
a solution in the cases of non-convex RCD-relations or disjunctive metric constraints.
Since in these cases both problems turn out to be intractable, an empirical evaluation of
the solutions is necessary to check scalability.
Acknowledgements.
This work has been partially supported by the Spanish Ministry
of Science and Innovation, the European Regional Development Fund of the European
Commission under grant TIN2009-14372-C03-01, and the Spanish MEC through the
project 15277/PI/10, funded by Seneca Agency of Science and Technology of the Re-
gion of Murcia within the II PCTRM 2007-2010. Guido Sciavicco and Angelo Monta-
nari were also partially founded by the Spanish fellowship 'Ramon y Cajal' RYC-2011-
07821 and by the Italian PRIN project
Innovative and multi-disciplinary approaches for
constraint and preference reasoning
, respectively.
References
1. Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the
ACM 26(11), 832-843 (1983)
2. Balbiani, P., Condotta, J.F., del Cerro, L.F.: A model for reasoning about bidimensional tem-
poral relations. In: Proc. of KR 1998, pp. 124-130 (1998)
3. Baykan, C.A., Fox, M.D.: Spatial synthesis by disjunctive constraint satisfaction. Artificial
Intelligence for Engineering Design, Analysis and Manufacturing 11(4), 245-262 (1997)
4. Borning, A., Kuang-Hsu Lin, R., Marriott, K.: Constraint-based document layout for the
web. Multimedia Syst. 8(3), 177-189 (2000)
5. Cohn, A.G., Hazarika, S.M.: Qualitative spatial representation and reasoning: An overview.
Fundamenta Informaticae 46(1-2), 1-29 (2001)
6. Condotta, J.F.: The augmented interval and rectangle networks. In: Proc. of KR 2000, pp.
571-579 (2000)
