SCIENCE@home

Rational Orthogonal Approximations to Orthogonal Matrices

V. Milenkovic,V. Milenkovic

Published 1993 in Computational geometry

ABSTRACT

Abstract 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 M 2 ( M , e ) with accuracy e and (2 b + 2)-bit numerators and a common (2 b + 2)-bit denominator (bit-size 2 b + 2), where b = ⌈− 1g e ⌉ ( e ≈ 2 − b ). The second algorithm uses basis reduction to generate an approximation M ν ( M , e ) with accuracy e ν 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 M opt ( M , e ) with accuracy e and bit-size proven to be no more than 1.5 b . 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 3 b bits for numerator and denominator. Applications are described for the approximation functions in the area of solid modeling.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-13 of 13 references · Page 1 of 1

CITED BY

Showing 1-12 of 12 citing papers · Page 1 of 1