TY - JOUR

T1 - Rational orthogonal approximations to orthogonal matrices

AU - Milenkovic, Victor J.

AU - Milenkovic, Veljko

N1 - Funding Information:
Certain numerical issues must be resolved in order to implement an algorithm of computational geometry as a computer program. The implementation can use exact or rounded arithmetic. If rounded arithmetic is used, it is necessary to deal with topological inconsistencies and numerical error. Exact arithmetic does not present these problems, but it has, in general, much higher cost than rounded arithmetic. Let us suppose we choose to use exact arithmetic. It is desirable that all operations be within the field of rational numbers. This is difficult to accomplish for constructions or computations involving * Corresponding author. 1 Supported by NSF grants NSF-CCR-91-157993 and NSF-CCR-90-09272. 2 Formerly affiliated with Ford Motor Company.

PY - 1997/1

Y1 - 1997/1

N2 - 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 Mv(M, ε) with accuracy εv/1.5 and bit-size vb for some 1.5 ≤ v ≥ 6 (but v 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 v ≈ 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.

AB - 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 Mv(M, ε) with accuracy εv/1.5 and bit-size vb for some 1.5 ≤ v ≥ 6 (but v 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 v ≈ 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.

KW - Computational geometry

KW - Polyhedral modeling

KW - Robust geometry

KW - Solids modeling

UR - http://www.scopus.com/inward/record.url?scp=8444250772&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=8444250772&partnerID=8YFLogxK

U2 - 10.1016/0925-7721(95)00048-8

DO - 10.1016/0925-7721(95)00048-8

M3 - Article

AN - SCOPUS:8444250772

VL - 7

SP - 25

EP - 35

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 1-2

ER -