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

✍ Scribed by Amar Isli; Anthony G. Cohn

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 515 KB
• Volume: 122
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/s0004-3702(00)00044-8

✦ Synopsis

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 introduction of RAs whose universe is a set of ternary relations: these support rotation as an operation in addition to those present in Tarski's formalisation. Then we propose two particular RAs: a binary RA, CYC b , whose universe 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 RA CYC t , more expressive than CYC b , constitutes a new approach to cyclic ordering of 2D orientations. An atom of CYC t expresses for triples of orientations whether each of the three orientations is equal to, to the left of, opposite to, or to the right of each of the other two orientations. CYC t has 24 atoms and the elements of its universe consist of all possible 2 24 subsets of the set of all atoms. Amongst other results,

(1) we provide for CYC t a constraint propagation procedure computing the closure of a problem under the different operations, and show that the procedure is polynomial, and complete for a subset including all atoms;

(2) we prove that another subset, expressing only information on parallel orientations, is NPcomplete;

(3) we show that provided that a subset S of CYC t includes two specific elements, 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 tractability to intractability if we add the universal relation to the set of all atoms.