INFDok - Dokumentenvolltextserver des Fachbereichs Informatik

Kurzfassung auf Englisch:

We propose a new approach to cyclic ordering of 2D orientations, consisting of a relation algebra (RA) whose universe is a set of ternary relations. An atom of the RA expresses for triples $(z_1,z_2,z_3)$ 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. The RA has $24$ atoms and the elements of its universe consist of all possible $2^{24}$ subsets of the set of all atoms. Because we are dealing with ternary relations, we add {\em rotation} as an operation in addition to those present in Tarski's formalisation of RAs. Amongst other results, (1) we provide for the RA a constraint propagation procedure computing the closure of a problem under the different operations, which we show is polynomial, and complete for a subset including all atoms; (2) we prove that another subset, expressing only information on parallel orientations, is NP-complete; (3) we show that provided that a subset ${\cal S}$ of the RA includes two specific elements, deciding consistency for a problem expressed in the closure of ${\cal S}$ can be polynomially reduced to deciding consistency for a problem expressed in ${\cal S}$; and (4) we derive from the previous result that we “jump” from tractability to intractability if we add the universal relation to the set of all atoms of the RA. A comparison to the most closely related work in the literature indicates that the approach is promising.