shortest route from point to point on discontinuous line
- From: gjvdkamp@xxxxxxxxx
- Date: Mon, 12 Nov 2007 12:21:28 -0000
Hi all,
I've been braking my head over this, and i'm just stuck. I'm writing
an algorithm that applies limits to a collection of objects and then
tries to find the largest subset of that collection that fits all
these limits.
Now one of these limits can be simplified to this situation.
Every point in my collection has an X and a Y value. One limit states
that the limit for the average value for Y is dependent on the average
value for X through this function:
LimitY(x) =
if x <= 36 then .5
if x > 36 and <= 39 then .45
if x > 39 and <= 42 then .41
if x > 42 and <= 45 then .38
if x > 45 and <= 48 then .36
if x > 48 then .33
so this limit is a line that looks something like this:
______
_____
_____
______
_______
To find out if the average for a certain collection, a point (x, y),
is above the line is easy, put the average for x into the function and
check if the average y is bigger than LimitY(x).
If the average is above the line, i have to delete some elements in
the collection to bring the average under the line. But i want to
delete as few objects as possible to bring it under the line. So take
these examples:
for points (X,Y)
* (48.1 , .35) in this case i would delete objectswith a large X to
bring down the average X to under 48. That would make the limit .36
and i would be ok.
* (47,9 , .37) in this case i would delete objects with a large Y to
bring down the average Y to .36.
* 48.1 , .37) in this case i woudl delete object with a large X and
a large Y, because the nearest point below the line is just to the
left and below.
Now i would like to find some generic algotithm that, for any point
(x,y), when above the limit, tells me if i should bring the average X
down, bring the average Y down, or maybe both.
So i need to find the shortest 'route' to a point below the line for
a given point (X, Y)
Does anyone have any experience with this type of problem? It's easy
to spot when you draw it out, but i'm finding it difficult to program
it with line segements and all.
Hope that one of you can give me some pointers,
Regards Gert-Jan
.
- Follow-Ups:
- Re: shortest route from point to point on discontinuous line
- From: Robert Israel
- Re: shortest route from point to point on discontinuous line
- Prev by Date: Re: request for books
- Next by Date: Re: Linear functionals on C(X)
- Previous by thread: New mathematics / physical sciences positions at http://jobs.phds.org, Nov 12, 2007
- Next by thread: Re: shortest route from point to point on discontinuous line
- Index(es):
Relevant Pages
|
Loading
