Using Galois Theory to Prove that Structure from Motion Algorithms are Optimal

Abstract

This talk presents a general method for establishing that a problem cannot 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. This results in a type of complexity theory for geometry problems. The method is based on Galois theory. It is applied to two well known structure from motion procedures: five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial, and L_2-optimal two-view triangulation, which can be realized by solving a sixth degree polynomial. It is shown that both these problems have been optimally solved in the sense that neither problem can be solved by even repeated root extraction of polynomials of any lesser degree. This rules out the possibility of undiscovered symmetries in the problems. It also follows that neither of these problems can be solved in closed form.

Graphics Seminar Home