# Intersection of Three Periodic Lines

This question is related to my earlier question, but on rethinking the problem I have come up with another solution that would be also acceptable.

I have three broken lines. Each has a constant gap of length $a$, a constant fill of length $b$ between them, and an offset $c$. Each line is something like $\lbrace t \mid a k < t+c < (a+b)k, k \in \mathbb{Z} \rbrace$ In the diagram below, I have plotted three example lines with respect to $t$.

In the diagram below, the areas where all three lines overlap is highlighted. I am interested in the first $t\ge0$ where this happens (perhaps that can be found from a general form of the lines' intersection). The lines plotted (top to bottom) have constants $a,b,c$ in pixels: $(60,72,-51)$, $(36,12,-4)$, and $(41,17,-18)$. The first $t$ satisfying all three lines is 196, so that would be the answer.

Basically, I'd be looking for the set intersection of the lines, as expressed above. I haven't been able to figure out how to do this. Another way might be to convolve three rectangle waves, and look at the result. Thoughts?

-
In general, I believe describing the intersection is a very hard dynamical systems problem, particularly if the ratios $b/c$ are independent over $\mathbb Q$ for the different lines. – Alex Becker Aug 4 '12 at 22:18
Are the lines always at a constant value? If so, then add all three of them: $f(t) = l_1(t)+l_2(t)+l_3(t)$. The intersecting areas will be the values of $t$ for which $f(t)$ is at its maximum. – Emily Aug 4 '12 at 22:21
Yes; the lines' $a$, $b$, and $c$ values remain constant. By add, I assume you mean add some equivalent rectangle waves, and find where their sum is first three. – imallett Aug 5 '12 at 7:37

## 1 Answer

If the first complete overlap usually comes as early as in your example, you don't have to worry about efficiency. Then you can use a sweep line algorithm: Keep three states with a Boolean value and a time in a priority queue ordered by the times; in each step take the upcoming item from the queue and flip its Boolean value; if all three Boolean values are true, terminate; else add either the gap or the fill length to the item, depending on its Boolean value, and insert it back into the queue.

-
I'd like the idea, but unfortunately the first complete overlap could be very distant--in fact infinite, so efficiency is pretty important. – imallett Aug 5 '12 at 7:35