An Algebra for Cyclic Ordering of 2D Orientations

Wedefine an algebra of ternary relations for cyclic ordering of 2Dorientations. Thealgebra (1) is a refinement 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. Wethen 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.

Authors

• Amar Isli Anthony G. Cohn

Keywords

No keywords are indexed for this paper.