A New Tractable Subclass of the Rectangle Algebra
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 442-446.
Abstract
This pap er presents the 169 permitted relations between two rectangles whose sides are para ll el to the axes of some orthogonal basis in a 2-dimensional Euclidean space. Elaborating rectangle algebra just like int erval algebra, it defines the concept of convexity as well as the ones of weak preconvexity and strong preconvexity. It introduces afterwards the fundamental operations of interse ct ion , composition and inversion and demonstrates that the concept of weak preconvexity is preserved by the operation of composition whereas the concept of strong preconvexity is preserved by th e operation of intersection. Finally, fitting the propagation techniques conceived to solve interval networks, it shows that the polynomial path-consistency algorithm is a decision method for the problem of proving the consistency of strongly preconvex r ecta ngle networks.
@inproceedings{ijcai1999p64,
title = {A New Tractable Subclass of the Rectangle Algebra},
author = {Balbiani, Philippe and Condotta, Jean-François and Fariñas del Cerro, Luis},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {442--446},
year = {1999},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1999/64},
}
TY - CPAPER TI - A New Tractable Subclass of the Rectangle Algebra AU - Balbiani, Philippe AU - Condotta, Jean-François AU - Fariñas del Cerro, Luis T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 442 EP - 446 UR - https://ijcai.org/proceedings/1999/64 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
