Rational orthogonal approximations to orthogonal matrices
Victor Milenkovic, Victor J. Milenkovic, Veljko Milenkovic, Veljko Milenkovic · Computational Geometry · 1997
Several algorithms are presented for approximating an orthogonal rotation matrix M in three dimensions by an orthogonal matrix with rational entries. The first algorithm generates an approximation M2(M, ε) with accuracy ε and (2b + 2)-bit numerators and a common (2b + 2)-bit denominator (bit-size 2b + 2), where b = ⌈− 1gε⌉ (ε ≈ 2−b). The second algorithm uses basis reduction to generate an approximation Mν(M, ε) with accuracy εν1.5 and bit-size νb for some 1.5 ≤ ν ≤ 6 (but ν cannot be controlled except by trial and error). A third algorithm, based on integer programming, generates optimal Mopt(M, ε) with accuracy ε and bit-size proven to be no more than 1.5b. In practice, the second algorithm generates an approximation with ν ≈ 1.5 and is much faster than the third algorithm. The best bit-sizes which one could obtain using previously known results in two dimensions (Canny et al., 1992) are more than 3b bits for numerator and denominator. Applications are described for the approximation functions in the area of solid modeling.