detect rolling channels in a series of high and low points

Question

Suppose that I have a sequence of lows and highs (1st and 2nd column respectively). The sequence length can be an arbitrary number. The length of 100 here is just an example.

$ awk -e 'BEGIN { for(i=1;i<=100;++i) { l=rand(); b=rand(); print l, l+b } }'
0.924046 1.51795
0.306394 0.885335
0.740133 1.52706
0.43637 0.768565
0.77888 0.879766
0.785084 1.62024
0.761209 1.25729
0.426298 1.3721
0.821802 1.53107
0.157828 0.27758
...

For each window of rows with size w (for example, if w=4, the windows will be rows1-4, rows2-5, ...), I want to find two lines $a1+bi$ and $a2+bi$ (channel) enclosing all the points in the window so that $|a2-a1|$ is minimized.

Is there an efficient algorithm to find channels like this?

The implementation can be in python and R.

Answer 1

Here is a brutal force way that should run in NWlogW time, that does not factor in the rolling window. I thought about some ways the rolling part can be used to cut down some running time, but overall the complexity level remains the same, so I won't bother there

First, find the convex hull or the 2W points in O(WlogW) time. The result is represented by all points on the border of the hull, and ordered in a list (up to O(W) in size).

Second, for each edge (formed by 2 adjacent points, except for the 2 vertical edges which we don't need), you can find the 'b' and 'a1'. Then find the furthest point on the convex hull by assuming a parallel line of slope 'b' going thru a point a find its corresponding 'a2'. this can be done in bi-sectional search and needs time LogW. Now, since there are O(W) edges, you need WlogW total time to find the edge-point combination that give you the smallest |a1-a2|

Third, you have O(N) windows. So the total time is O(NWlogW). I guess this is not a very efficient way, but can give you an upper bound of doing this.