New, faster, more controlled fitting of implicit polynomial 2D curves and 3D surfaces to data

Denote a point in the plane by z=(z,y) and a polynomial of nth degree in z by f(z) Σ_i,j⩾o₁i+j⩽n(a _ijxⁱy^j). Denote by Z(f) the set of points for which f(z)=0. Z(f) is the 2D curve represented by f(z). In this paper, we present a new approach to fitting 2D curves to data in the plane (or 3D surfaces to range data) which has significant advantages over presently known methods. It requires considerably less computation and the resulting curve can be forced to lie close to the data set at prescribed points provided that there is an nth degree polynomial that can reasonably approximate the data. Linear programming is used to do the fitting. The approach can incorporate a variety of distance measures and global geometric constraints