ols6000 wrote: >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. > >I agree. > >> 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.
I looked at it again. I think my proof that there is an optimal lower bounding line through at least two points is good.
Based on that result, O(N^2) is automatic.
>> 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.
The nonnegativity of y_i - y(x_i) for i = 1..N is what I mean by saying that L is a lower bounding line.
>> 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.
Right. I take back my claim of O(N). In general, the convex hull procedure as I described it may need multiple passes. I wonder how many passes would be needed, in the worst case, as a function of N.
>>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)?
Right, my suggested simplification fails.
In fact, I don't see how convex closure can be guaranteed to work in O(N). But it certainly can be accomplished in O(N^2), in the worst case by testing the lines between all pairs of points, checking to see which of the lines are lower bounding lines, and of those, choosing one which minimizes s.