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

Papers 1

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.