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 ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 8, 2013 5:25 AM

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.

>

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.

quasi

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