On Sunday, July 7, 2013 6:43:41 PM UTC-7, quasi wrote: > Firstly, it's clear that if y = ax + b is an optimal bounding > line, then it must pass through one of the N points, otherwise > b can be increased , contrary to minimality of the sum.
> But in fact, I'll show that there is an optimal line which passes > through at least two of the N points, not just one.
It seems likely, but I don't follow your proof.
> Let s = SUM(y_i - y(x_i)). > > Since L is an optimal bounding line, s is minimal
But here you haven't taken into account that y_i - y(x_i) must be >=0. s is only minimal subject to this condition.
> Next, we get a kind of a convex hull for the piecewise linear > function determined by the vertices (x_i,y_i). > To do this, make one pass through the list of N points, removing > from the list any point (x_i,y_i) which is such that it is above > or on the line through its two neighbors. Once a point is dropped, > it's no longer a neighbor. Neighbors of a currently live point > are the live points with closest left and right x values. > > After one such removal pass, the piecewise function through > the remaining vertices is a convex function.
This procedure will not produce a convex piecewise function in a single pass, as I understand your algorithm. Here is a counter-example: x y 0 0 1 20 2 25 3 40 4 45 5 70 6 80
During one pass we remove 25 and 45, leaving segments with slopes 1/20, 2/20, and 2/30. Intuitively, what is happening is that points that were used as right neighbors are then deleted one step later.
> The algorithm as described above is O(N).
Only true if the "convex hull" can be determined in a single pass.
>With a slight adjustment of my previous argument, one of the >N-1 lines through the points (x_i,y_i) and (x_(i+1),y_(i+1)) >for i = 1..(N-1) is an optimal lower bounding line.
This is definitely not true. Here is a counter-example:
x y 0 0 1 5 2 10 3 25
The optimum bounding line passes through (0,0) and (3,25). That line doesn't pass through any consecutive pair of points.
Your two-point idea is good, and can clearly be used for an O(n^2) method. Can you refine your method for getting a convex piecewise function so it is O(n)?