Qualitative spatial reasoning: A new approach to cyclic ordering of 2D orientations

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