Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: How to find a bounding line?
Replies: 39   Last Post: Jul 12, 2013 5:39 AM

 Messages: [ Previous | Next ]
 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 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.

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.

> 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)?

Date Subject Author
7/7/13 Woody
7/7/13 Scott Berg
7/7/13 Peter Percival
7/7/13 Woody
7/7/13 quasi
7/7/13 quasi
7/8/13 quasi
7/8/13 Woody
7/8/13 quasi
7/8/13 LudovicoVan
7/8/13 LudovicoVan
7/10/13 Woody
7/10/13 quasi
7/8/13 Leon Aigret
7/8/13 Woody
7/10/13 Leon Aigret
7/10/13 Leon Aigret
7/10/13 Woody
7/10/13 RGVickson@shaw.ca
7/10/13 Woody
7/10/13 quasi
7/7/13 quasi
7/7/13 quasi
7/7/13 quasi
7/8/13 William Elliot
7/8/13 Peter Percival
7/8/13 quasi
7/11/13 Woody
7/11/13 quasi
7/11/13 LudovicoVan
7/11/13 quasi
7/11/13 Leon Aigret
7/11/13 Woody
7/11/13 Leon Aigret
7/12/13 Woody
7/12/13 Leon Aigret
7/11/13 Woody
7/12/13 quasi
7/12/13 Woody
7/12/13 quasi