Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Woody

Posts: 44
Registered: 7/29/09
Re: How to find a bounding line?
Posted: Jul 8, 2013 3:11 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 [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 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
Read How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
Scott Berg
7/7/13
Read Re: How to find a bounding line?
Peter Percival
7/7/13
Read Re: How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Woody
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Leon Aigret
7/8/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
RGVickson@shaw.ca
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
William Elliot
7/8/13
Read Re: How to find a bounding line?
Peter Percival
7/8/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
LudovicoVan
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.