Fitting a least squares piecewise linear continuous curve in two dimensions

An optimal piecewise linear continuous fit to a given set of n data points D = {(x(i),yi) : 1 less than or equal to i less than or equal to n} in two dimensions consists of a continuous curve defined by k linear segments {L-1 , L-2,..., L-k} which minimizes a weighted least squares error function wit h weight w(i) at (x(i),y(i)), where k greater than or equal to 1 is a given integer. A key difficulty here is the fact that the linear segment L-j, wh ich approximates a subset of consecutive data points D-j subset of D in an optimal solution, is not necessarily an optimal fit in itself for the point s D-j. We solve the problem for the special case k = 2 by showing that an o ptimal solution essentially consists of two least squares linear regression lines in which the weight w(j) of some data point (x(j), y(j)) is split in to the weights lambdaw(j) and (1 - lambda )w(j), 0 less than or equal to la mbda less than or equal to 1, for computations of these lines. This gives a n algorithm of worst-case complexity O(n) for finding an optimal solution f or the case k = 2. (C) 2001 Elsevier Science Ltd. All rights reserved.