A Qualitative Calculus for Three-Dimensional Rotations

Azam Asl, Ernest Davis

Research output: Contribution to journalArticlepeer-review

Abstract

We have developed a qualitative calculus for three-dimensional directions and rotations. A direction is characterized in terms of the signs of its components relative to an absolute coordinate system. A rotation is characterized in terms of the signs of the components of the associated 3 × 3 rotation matrix. A system has been implemented that can solve the following problems: 1. Given the signs of direction and rotation matrix P, find the possible signs of the image of under P. Moreover, for each possible sign vector of · P, generate numerical instantiations of and P that yields that result. 2. Given the signs of rotation matrices P and Q, find the possible signs of the composition P · Q. Moreover, for each possible sign matrix for the composition, generate numerical instantiations of P and Q that yield that result. We have also proved some related complexity and expressivity results. The satisfiability problem for a qualitative rotation constraint network is NP-complete in two dimensions and NP-hard in three dimensions. In three dimensions, any two directions are distinguishable by a qualitative rotation constraint network.

Original languageEnglish (US)
Pages (from-to)18-57
Number of pages40
JournalSpatial Cognition and Computation
Volume14
Issue number1
DOIs
StatePublished - 2014

Keywords

  • qualitative calculus
  • qualitative spatial reasoning
  • three-dimensional rotation

ASJC Scopus subject areas

  • Modeling and Simulation
  • Experimental and Cognitive Psychology
  • Computer Vision and Pattern Recognition
  • Earth-Surface Processes
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'A Qualitative Calculus for Three-Dimensional Rotations'. Together they form a unique fingerprint.

Cite this