Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 5, October 2002: pp. 885-909

Tractability Results in the Block Algebra

Philippe Balbiani1, Jean-François Condotta1 and Luis Fariñas Del Cerro1

1Institut de Recherche en Informatique de Toulouse, 118, route de Narbonne, F-31062 Toulouse cedex 04, France. E-mail: {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 p-dimensional 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 13p 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 NP-complete. 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 ORD-Horn representability are the same.

Keywords: Spatial reasoning; qualitative constraints; consistency problem; interval algebra; block algebra

Table of Contents   Full-Text PDF (235 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement