Characterization of 3D bijective digitized rotations


Euclidean rotations in \(\mathbb{R}^n\) are bijective and isometric maps. Nevertheless, they lose these properties when digitized in \(\mathbb{Z}^n\). For \(n=2\), the subset of bijective digitized rotations has been described explicitly by Nouvel and Rémila and more recently by Roussillon and Cœurjolly. In the case of 3D digitized rotations, the same characterization has remained an open problem.

We have been studied the problem and up-to-date, we have proposed an algorithm for certifying the bijectivity of 3D digitized rational rotations using the arithmetic properties of the Lipschitz quaternions. In Bijectivity Certification of 3D Digitized Rotations we introduced an algorithm to verify whether a 3D digitized rotation induced by a Lipschitz quaternion is bijective or not (see QuaternionCertification DOI).

Currently, we are working on the analytical characterization of 3D bijective digitized rotations. We invite anybody who would like to work on this project to start from studying the properties of some Lipschitz quaternions certified by our algorithm as ones which lead to 3D bijective digitized rotations.

The list of such quaternions, which induce bijective digitized rotations, from the range \([-10,10]^4\) can be downloaded from (please click the DOI badge DOI).

Also, the list of quaternions from the range \([-10,10]^4\), which do not induce 3D bijective digitized rotations can be downloaded from (please click the DOI badge DOI).

How to cite

Any results obtained with the algorithm should cite Bijectivity Certification of 3D Digitized Rotations.


Special thanks for Éric Andres of the University of Poitiers, XLIM for pointing out a bug in an early implementation of the algorithm.

Many thanks for Victor Ostromoukhov of University of Lyon 1, LIRIS, France, for pointing out that the list of Lipschitz quaternions given in the paper is not complete, and this led us to a discovery of a bug in our code. The current list of Lipschitz quaternions which induce bijective digitized rotations (see the link above) contain 576 more quaternions than the one to which link was given in the paper.