Woody
Posts:
44
Registered:
7/29/09


Re: How to find a bounding line?
Posted:
Jul 8, 2013 3:11 AM


On Sunday, July 7, 2013 6:43:41 PM UTC7, 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 [edit], 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.
> 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 counterexample: 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 >N1 lines through the points (x_i,y_i) and (x_(i+1),y_(i+1)) >for i = 1..(N1) is an optimal lower bounding line.
This is definitely not true. Here is a counterexample:
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 twopoint 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)?

