Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

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?

share|cite|improve this question
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

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.