Skip to Main content Skip to Navigation
Conference papers

A new tractable subclass of the rectangle algebra

Abstract : This paper presents the 169 permitted relations between two rectangles whose sides are parallel to the axes of some orthogonal basis in a 2-dimensional Euclidean space. Elaborating rectangle algebra just like interval 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 intersection, 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 the 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 rectangle networks.
Document type :
Conference papers
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03300314
Contributor : Fabien Delorme <>
Submitted on : Thursday, September 2, 2021 - 9:51:24 AM
Last modification on : Saturday, September 4, 2021 - 3:20:07 AM

File

064.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03300314, version 1

Citation

Philippe Balbiani, Jean-François Condotta, Luis Farinas del Cerro. A new tractable subclass of the rectangle algebra. Sixteenth International Joint Conference on Artificial Intelligence (IJCAI 1999), The International Joint Conferences on Artificial Intelligence, Inc., 1999, Stockholm, Sweden. pp.442-447. ⟨hal-03300314⟩

Share

Metrics

Record views

16

Files downloads

13