OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation
Journal of Logic and Computation
Volume 12, Issue 5, October 2002: pp. 885909
Tractability Results in the Block Algebra
Philippe Balbiani^{1}, JeanFrançois Condotta^{1} and Luis Fariñas Del Cerro^{1}
^{1}Institut de Recherche en Informatique de Toulouse, 118, route de Narbonne, F31062 Toulouse cedex 04, France. Email: {balbiani,condotta,farinas}@irit.fr
In this paper we define the notion of a block algebra, which is based upon a spatial application of Allen's interval algebra. In the pdimensional Euclidean space, where p [ge] 1, we consider only blocks whose sides are parallel to the axes of some orthogonal basis. The block algebra consists of a set of relations (the block relations) together with the fundamental operations of composition, converse and intersection. The 13^{p} basic relations of this algebra constitute the exhaustive list of the relations possibly holding between two blocks. We are interested in the problem of testing the consistency of a set of spatial constraints between blocks, i.e. a block network. The consistency question for block networks is NPcomplete. We first extend the notions of convexity and preconvexity to the block algebra. Similarly to the interval algebra case, convexity leads to a tractable set whereas, contrary to the interval algebra case, preconvexity leads to an intractable set. Nevertheless we characterize a tractable subset of the preconvex relations: the strongly preconvex relations. Moreover we show that strong preconvexity and ORDHorn representability are the same.
Keywords: Spatial reasoning; qualitative constraints; consistency problem; interval algebra; block algebra
Table of Contents
FullText PDF (235 KB)
