Where and rank(A) = n, then the solution is overdetermined; i.e. we have more than the minimum number of points required to fit the given surface. It may be that a surface can be formed which passes through all of the given points, but in general this is unlikely so a best fit is required. There are a number of solutions to this problem; the one given to minimise the least square geometric error is from Pratt. The algorithm is stated as follows, but a discussion and proof of the approach can be found in Lawson and Hanson.

• Given A as above, of size m by n, compute the Cholesky decomposition . That is compute the unique n by n upper triangular matrix, U, with non-negative diagonal entries such that .

  (In an upper triangular matrix, for j < i. )

• Delete the last row of U to yield an by n matrix. Then treat this matrix as if it were A in the exact fit case, i.e. append a row of polynomials and compute the determinant. the resulting surface is the best fit subject to holding the n'th coefficient of the polynomial constant.

For example, consider again the planar case; assume we have 4 points.

Then we form the matrix, A,

and is

and is

Substitute the several terms in the above matrix by constants, since each is computed from the set of data points. Hence and so on. The matrix is now

Compute the Cholesky decomposition. Then U is defined as (in list format),

Deleting the last line, and replacing with the basis set of the plane, we define the equivalent polynomial matrix to Equation 39

Replacing the constant, non-zero coefficients we have the solution as the determinant,

which is

As an example, we show a depth image below and a segmentation into surface patches. In fact, the problem was constrained by the knowledge that only planar and cylindrical patches were in the scene, and the classification is quite good.