An Algebra for Cyclic Ordering of 2D Orientations

Abstract

We define an algebra of ternary relations for cyclic or-dering of 2D orientations. The algebra (1) is a refine-ment of the CYCORD theory; (2) contains 24 atomic relations, hence 224 general relations, of which the usual CYCORD relation is a particular relation; and (3) is NP-complete, which is not surprising since the CYCORD theory is. We then provide: (1) a constraint propagation algorithm for the algebra, which we show is polynomial, and complete for a subclass including all atomic relations; (2) a proof that another subclass, expressing only information on parallel orientations, is NP-complete; and (3) a solution search algorithm for general problem expressed in the algebra.