A new approach to cyclic ordering of 2D orientations using ternary relation algebras

In Tarski's formalisation, the universe of a relation algebra (RA) consists of a set of binary relations. A first contribution of this work is the int roduction of RAs whose universe is a set of ternary relations: these suppor t rotation as an operation in addition to those present in Tarski's formali sation. Then we propose two particular RAs: a binary RA, CYCb, whose univer se is a set of (binary) relations on 2D orientations; and a ternary RA, CYC t, whose universe is a set of (ternary) relations on 2D orientations. The R A CyCt, more expressive than CYCb, constitutes a new approach to cyclic ord ering of 2D orientations. An atom of CYCt expresses for triples of orientat ions whether each of the three orientations is equal to, to the left of, op posite to, or to the right of each of the other two orientations. CYCt has 24 atoms and the elements of its universe consist of all possible 2(24) sub sets of the set of all atoms. Amongst other results, (1) we provide for CyCt a constraint propagation procedure computing the cl osure of a problem under the different operations, and show that the proced ure is polynomial, and complete for a subset including all atoms; (2) we prove that another subset, expressing only information on parallel o rientations, is NP-complete; (3) we show that provided that a subset S of CYCt includes two specific ele ments, deciding consistency for a problem expressed in the closure of S can be polynomially reduced to deciding consistency for a problem expressed in S; and (4) we derive from the previous result that for both RAs we "jump" from tra ctability to intractability if we add the universal relation to the set of all atoms. A comparison to the most closely related work in the literature indicates that the approach is promising. (C) 2000 Elsevier Science B.V. Al l rights reserved.