Finding maximum increases
Sorry Found a mistake. I'm still certain that all the max slopes contain the max slopes of interval 1. But I found out that the 3rd highest could be the entire set. It's probally still doable, but the worst case could be bad. I'll think about it a little more and see if I can fix it.
hmmm.... looks kinda like constructing map for self-shadowing, but i don't understand why you need averaging.
and ideas:
first, try to do something based on divide and conquer. Try to make fast enough algorithm for merging 2 results into one, then you just recursively do first half, second half, and merge 'em, like sorting.
edit: note that you need to consider only convex hull of right part when you merge two results together. And max slope points on convex hull can be found using something like binary search for maximum. So merge probably can be done in in O(N log N) time, and therefore entire problem too.
and ideas:
first, try to do something based on divide and conquer. Try to make fast enough algorithm for merging 2 results into one, then you just recursively do first half, second half, and merge 'em, like sorting.
edit: note that you need to consider only convex hull of right part when you merge two results together. And max slope points on convex hull can be found using something like binary search for maximum. So merge probably can be done in in O(N log N) time, and therefore entire problem too.
Quote:Original post by Cocalus
Sorry Found a mistake. I'm still certain that all the max slopes contain the max slopes of interval 1. But I found out that the 3rd highest could be the entire set. It's probally still doable, but the worst case could be bad. I'll think about it a little more and see if I can fix it.
Thanks for the idea. I like the idea where I don't have to compare every point with every other point. (although some simple optimizations could probably cut this down a lot)
However, I just found a case where I think that your algorithm will break. Maybe not, I'm not 100% sure how it works. Consider this:
| *
|
|
| *
|* *
| *
+---------
1 2 3 4 5
The slope between 1 and 3 is large, 1 and 4 smaller, then 1 and 5 largest. I'm not positive if this breaks your algo, but it might if I am understanding you correctly.
I'm not at home atm, but when I am, I will code the easy solution to the problem and see if it is sufficiently fast. It might be the case where it is easiest to simply start with the 'slow' algo and then find special cases where I can avoid computation in order to speed it up.
I'll post as soon as I get some results, but in the meantime, I wouldn't mind more ideas incase a hacked version of the brute force algo isnt fast enough.
Thanks
Dwiel
Do you have integers on the y axis or floats?
I can tell you where a section of the greatest slopes are after one pass (explained above) but I'm trying to find a good way to figure out when to stop searching for them is. The exception I found is
| *
| ************.........******
|*
+-------------.........-------
The 3 biggest slopes are 1 to 2,n-1 to n, and 1 to n.
I can tell you where a section of the greatest slopes are after one pass (explained above) but I'm trying to find a good way to figure out when to stop searching for them is. The exception I found is
| *
| ************.........******
|*
+-------------.........-------
The 3 biggest slopes are 1 to 2,n-1 to n, and 1 to n.
Quote:Original post by CocalusNo. The function si j was given i = 1 in his example. 4 to 5 is the largest slope, but that's i = 4. edit: Doh! you realized this seconds before I posted.
It doesn't 4 to 5 is the largest.
Is the y-axis integers (or could effectifly turned into integers) or floats and what kind of range does it have?
Author
The range depends on the set. They should all be between 0~500 with two digits after the decimal. Maybe 3
Dwiel
Dwiel
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
