Qualitative Spatial Reasoning à la Allen: An Algebra for Cyclic Ordering of 2D Orientations

Amar Isli and Anthony G. Cohn

We define an algebra of ternary relations for cyclic ordering of 2D orientations, which is a refinement of the CYCORD theory. The algebra (1) contains 24 atomic relations, hence 2^{24} general relations, of which the usual CYCORD relation is a particular relation; and (2) is NP-complete, which is not surprising since the CYCORD theory is. We then provide the following: (1) a constraint propagation algorithm for the algebra; (2) a proof that the propagation algorithm is polynomial, and complete for a subclass including all atomic relations; (3) a proof that another subclass, expressing only information on parallel orientations, is NP-complete; and (4) a solution search algorithm for a general problem expressed in the algebra. A comparison to related work indicates that the approach is promising.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.