Using Galois Theory to Prove Structure from Motion Algorithms are Optimal

This paper presents a general method, based on Galois theory, for establishing that a problem can not be solved by a ´machine´ that is capable of the standard arithmetic operations, extraction of radicals (that is, m-th roots for any m), as well as extraction of roots of polynomials of degree smaller than n, but no other numerical operations. The method is applied to two well known structure from motion problems: five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial [6], and L2-optimal two-view triangulation, which can be realized by solving a sixth degree polynomial [3]. It is shown that both these solutions are optimal in the sense that an exact solution intrinsically requires the solution of a polynomial of the given degree (10 or 6 respectively), and cannot be solved by extracting roots of polynomials of any lesser degree.