The Puzzle Thread!

[nslay]

I'm pretty sure this is The Puzzle Thread not The Math Thread.  Knock it off...

I didn't know there was a difference. Do you like your math served up in words, or chopped into numbers?

Maybe that's how we can persuade people to like math ... we can rename the subject to "Puzzles" or "Solving Puzzles"!

[nslay]

Given two lines in 1D of lengths [latex]\ell_1,\ \ell_2[/latex] each centered at [latex]x_1,\ x_2 \in \mathbb{R}[/latex], find the overlap of the lines. For example, if [latex]x_1 = 0,\ x_2 = \frac{1}{2}[/latex] and [latex]\ell_1 = \ell_2 = 1[/latex] then the overlap should be [latex]\frac{1}{2}[/latex].

It has a relatively simple solution, though it does not appear to be as simple to derive as would be expected. Perhaps I'm over thinking it. I want to see if anyone can find an easier derivation.

I'll post my derivation in a day or upon seeing a derivation.

EDIT: Oh yeah, I think I found an easier way. I'll post both solutions.

[nslay]

My original solution:

My idea was to represent each line as a box car function. The integral of the box car function is the length of it's non-zero portion. Thus, the integral of the product of the two box car functions would be the length of the overlap.

So we have two lines
[latex]
\Pi_{-\ell_1/2,\ell_1/2}(x - x_1) = H(x - x_1 + \ell_1/2) - H(x-x_1-\ell_1/2)
\Pi_{-\ell_2/2,\ell_2/2}(x - x_2) = H(x - x_2 + \ell_2/2) - H(x-x_2-\ell_2/2)
[/latex]
where [latex]H(\cdot)[/latex] is the Heaviside function

Then, the overlap is given by the integral
[latex]
\text{overlap} = \int_{-\infty}^{\infty} \Pi_{-\ell_1/2,\ell_1/2}(x-x_1) \Pi_{-\ell_2/2,\ell_2/2}(x-x_2) dx
[/latex]

First note that
[latex]
\frac{d}{dx} \left [ \Pi_{-\ell_1/2,\ell_1/2}(x-x_1) \right ] = \delta(x-x_1+\ell_1/2) - \delta(x-x_1-\ell_1/2)
\int \Pi_{-\ell_2/2,\ell_2/2}(x-x_2) dx = (x - x_2 + \ell_2/2) I(x - x_2 + \ell_2/2 > 0) - (x - x_2 - \ell_2/2) I(x - x_2 - \ell_2/2 > 0)
[/latex]
where [latex]\delta(\cdot)[/latex] denotes the Dirac delta function and [latex]I(\cdot)[/latex] denotes the indicator function.

By integrating by parts, we can simplify the integral
[latex]
\int_{-\infty}^{\infty} \Pi_{-\ell_1/2,\ell_1/2}(x-x_1) \Pi_{-\ell_2/2,\ell_2/2}(x-x_2) dx = \left . \left [ \Pi_{-\ell_1/2,\ell_1/2}(x-x_1) \int \Pi_{-\ell_2/2,\ell_2/2}(x-x_2) dx \right ] \right |_{-\infty}^{\infty}
- \int_{-\infty}^{\infty} \underbrace{[ (x - x_2 + \ell_2/2) I(x - x_2 + \ell_2/2 > 0) - (x - x_2 - \ell_2/2) I(x - x_2 - \ell_2/2 > 0) ]}_{\int \Pi_{-\ell_2/2,\ell_2/2}(x-x_2) dx} \underbrace{[ \delta(x-x_1+\ell_1/2) - \delta(x-x_1-\ell_1/2) ]}_{\frac{d}{dx} \left [ \Pi_{-\ell_1/2,\ell_1/2}(x-x_1) \right ] } dx
[/latex]

The first term cancels since [latex]\Pi_{-\ell_1/2,\ell_1/2}(\pm \infty-x_1) = 0[/latex]. The second term is trivial to compute since
[latex]
\int_{-\infty}^{\infty} f(x) \delta(x-a) dx = f(a)
[/latex]

This gives
[latex]
\int_{-\infty}^{\infty} \Pi_{-\ell_1/2,\ell_1/2}(x-x_1) \Pi_{-\ell_2/2,\ell_2/2}(x-x_2) dx = - (x_1 - \ell_1/2 - x_2 + \ell_2/2) I(x_1 - \ell_1/2 - x_2 + \ell_2/2 > 0)
+ (x_1 - \ell_1/2 - x_2 - \ell_2/2) I(x_1 - \ell_1/2 - x_2 - \ell_2/2 > 0)
+ (x_1 + \ell_1/2 - x_2 + \ell_2/2) I(x_1 + \ell_1/2 - x_2 + \ell_2/2 > 0)
- (x_1 + \ell_1/2 - x_2 - \ell_2/2) I(x_1 + \ell_1/2 - x_2 - \ell_2/2 > 0)
[/latex]

If we write [latex]\Delta x = x_1 - x_2,\ u = \frac{\ell_1+\ell_2}{2},\ v = u - \ell_2[/latex] then we have a more simplified form

[latex]
\text{overlap}(x_1,x_2,\ell_1,\ell_2) = - (\Delta x - v) I(\Delta x - v > 0)
+ (\Delta x - u) I(\Delta x - u > 0)
+ (\Delta x + u) I(\Delta x +u > 0)
- (\Delta x + v) I(\Delta x + v > 0)
[/latex]

It's a nifty looking solution. In C it would be

Code Select Expand


double x1, x2, l1, l2, dx, u, v, tmp, L;

dx = x1 - x2;
u = 0.5*(l1+l2);
v = u - l2;

tmp = dx - v;
L = -tmp*(tmp > 0);
tmp = dx - u;
L += tmp*(tmp > 0);
tmp = dx + u;
L += tmp*(tmp > 0);
tmp = dx + v;
L -= tmp*(tmp > 0);


One could do a more direct solution by considering the end points of the lines instead of the midpoints. Then it's a lot easier to derive directly and reduces to 4 possible if conditions. That matches the 4 indicator functions the integration gives (indicators are like branchless if statements).

EDIT: Fixed some errors (Forgot to divide by 2 in some places).