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 ]
quasi

Posts: 10,307
Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 8, 2013 5:25 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 [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.


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
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.