Qual it at i ve Spat i al Reasoni ng a la Al l en: An Al gebr af or Cycl ic Or der i ng of 2D Or i ent at i ons

摘要: We define an algebra of ternary relations for cyclic or der i ng of 2D orientations, which is a refinement of t he CYCORD theory. The algebra (1) contains 24 atomic relations, hence 224 general relations, of which t he usual CYCORD relation is a particular relation; and (2) is NP-compl et e, whi ch is not surprising since t he CYCORD theory is. We then provide the following:(1) a constraint propagation algorithm for the algebra;(2) a proof that the propagation algorithm is pol ynomi al, and compl et ef or a subcl ass i ncl udi ng all atomic relations;(3) a proof that another subclass, expressing only information on parallel orientations, is NP-complete; and (4) a solution search algorithm for a general probl em expressed in the algebra. A compar i son tor el at ed wor ki ndi cat es t hat t he appr oach is pr omi si ng.