## 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 language | English (US) |
---|---|

Pages (from-to) | 18-57 |

Number of pages | 40 |

Journal | Spatial Cognition and Computation |

Volume | 14 |

Issue number | 1 |

DOIs | |

State | Published - 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