Research and Advances

Least squares fitting of planes to surfaces using dynamic programming

Dynamic programming has recently been used by Stone, by Bellman and by Gluss to determine the closest fit of broken line segments to a curve in an interval under the constraint that the number of segments is fixed. In the present paper successive models are developed to extend the method to the fitting of broken plane segments to surfaces z = g(x, y) defined over certain types of subareas of the (x, y)-space. The first model considers a rectangular area, with the constraint that the plane segments are defined over a grid in the (x, y)-space. It is then shown how this model may be incorporated into an algorithm that provides successive approximations to optimal fits for any type of closed area. Finally, applications are briefly described.

Advertisement

Author Archives

Research and Advances

Further remarks on line segment curve-fitting using dynamic programming

In a recent paper, Bellman showed how dynamic programming could be used to determine the solution to a problem previously considered by Stone. The problem comprises the determination, given N, of the N points of subdivision of a given interval (&agr;, &bgr; and the corresponding line segments, that give the best least squares fit to a function g(x) in the interval. Bellman confined himself primarily to the analytical derivation, suggesting briefly, however, how the solution of the equation derived for each particular point of subdivision ui could be reduced to a discrete search. In this paper, the computational procedure is considered more fully, and the similarities to some of Stone's equations are indicated. It is further shown that an equation for u2 involving no minimization may be found. In addition, it is shown how Bellman's method may be applied to the curve-fitting problem when the additional constraints are added that the ends of the line segments must be on the curve.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved