Groebner-basis solution of the three-dimensionalresection problem (P4P)

Abstract

The three-dimensional (3-D) resection problemis usually solved by first obtaining the distancesconnecting the unknown point {X; Y ; Z} to the known points {Xi; Yi; Zi}/ i= 1, 2, 3 through the solution of the three nonlinear Grunert equations and then using the obtained distances to determine the position {X, Y, Z} and the 3-D orientation parameters. Starting from the work of the German J. A.Grunert (1841), the Grunert equations have been solved in several substitutional steps and the desire as evidenced by several publications has been to reduce these number of steps. Similarly, the 3-D ranging step for position determination which follows the distance determination step involves the solution of three nonlinear ranging ('Bogenschnitt') equations solved in several substitution steps. It is illustrated how the algebraic technique of Groebner basis solves explicitly the nonlinear Grunert distance equations and the nonlinear 3-D ranging ('Bogenschnitt') equations in a single step once the equations have been converted into algebraic (polynomial) form. In particular, the algebraic tool of the Groebner basis provides symbolic solutions to the problem of 3-D resection. The various forward and backward substitution steps inherent in the classical closed-form solutions of the problem are avoided. Similar to the Gauss elimination technique in linear systems of equations, the Groebner basis eliminates several variables in a multivariate system of nonlinear equations in such a manner that the end product normally consists of a univariate polynomial whose roots can be determined by existing programs e.g. by using the roots command in Matlab.