A tractable subclass of the block algebra : constraint propagation and preconvex relations
Abstract
We define, in this paper, for every n ≥ 1, n-dimensional block algebra as a set of relations, the block relations, together with the fundamental operations of composition, conversion and intersection. We examine the 13n atomic relations of this algebra which constitute the exhaustive list of the permitted relations that can hold between two blocks whose sides are parallel to the axes of some orthogonal basis in the n-dimensional Euclidean space over the field of real numbers. We organize these atomic relations in ascending order with the intention of defining the concept of convexity as well as the one of preconvexity. We will confine ourselves to the issue of the consistency of block networks which consist of sets of constraints between a finite number of blocks. Showing that the concepts of convexity and preconvexity are preserved by the fundamental operations, we prove the tractability of the problem of the consistency of strongly preconvex block networks, on account of our capacity for deciding it in polynomial time by means of the path-consistency algorithm.