An Algebra for Cyclic Ordering of 2D Orientations

Amar Isli, Anthony G. Cohn

We define an algebra of ternary relations for cyclic ordering of 2D orientations. The algebra (1) is a refinement of the CYCORD theory; (2) contains 24 atomic relations, hence 2^24 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 inculding 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 a general problem expressed in the algebra.

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.