Sunday 9 August 2009

## Homework Answers

Seems like a few people got close to the answer for the first problem. You formulate the condition for * q* being on the circle as a quadratic equation in

*t*, and then apply the quadratic formula to solve for

*t*. However, I can't give full credit to anyone because all the answers were incomplete; many ended containing a "plus or minus the square root ..." but a complete answer must describe which solution to pick. It's pretty easy to figure that out though.

My answer is*t* = (*a**x* + *b**y* - √(*r*²(*x*² + *y*²) - (*a**y* - *b**x*)²))/(*a*² + *b*² - *r*²)

where * p* = (

*a*,

*b*) and

*= (*

**q***x*,

*y*). The answer from Wolfram Alpha via Neil Rashbrooke is the same except it chooses the positive root; I think that's wrong, because it will give you a negative

*t*(the denominator is negative).

The second problem is harder. Even though it's intuitively "obvious" that a solution is always possible, I found it quite difficult to prove, and apparently so did my readers. I think Joshua Cranmer got close but I don't fully understand his answer and he didn't get a complete algorithm for finding the order.

I start by observing that if you can find one rectangle to move safely then the solution to the whole problem follows by induction, since one moved rectangle can never overlap other moved rectangles, since they didn't overlap to start with. So the problem is reduced to finding one rectangle to move safely from the set of rectangles.

I also observe that without loss of generality you can reduce the problem to the case where the components of * v* are non-negative, i.e., we are moving the rectangles down and to the right by some amount, possibly zero.

Let's say rectangles *R* and *S* **overlap horizontally** if their projections onto the x-axis intersect. Similarly, they **overlap vertically** if their projections onto the y-axis intersect. Because our rectangles are non-overlapping, if *R* and *S* are different and overlap horizontally they cannot overlap vertically, and either *R* is **entirely above** *S* (every point in *R* is above (or on) the top edge of *S*) or *R* is **entirely below** *S* (every point in *R* is below (or on) the bottom edge of *S*).

Consider the subset of rectangles *R* such that *R* has no rectangle entirely below it that it overlaps horizontally. These rectangles do not overlap each other horizontally. Choose the "rightmost" rectangle from this set, let's call it *M*. I claim no other rectangle intersects *M* + **v**. This solves the problem.

The proof is still subtle. We have to show that our subset is non-empty, i.e., that at least one rectangle has no rectangles below it that it overlaps horizontally. This is easy though, since rectangle with the lowest bottom-edge certainly has no rectangles below it. So such an *M* exists.

Of course the hard part is to show that no other rectangle intersects *M* + * v*. We can show that in fact no rectangles are below

*M*'s top edge and to the right of

*M*'s left edge (other than

*M*itself). Let's call this set

*S*. I'll show

*S*is empty, by assuming

*S*is nonempty and working to a contradiction.

Clearly there can be no rectangles below *M*'s top edge that overlap *M* horizontally, or they would have to be below *M* and we wouldn't have put *M* in that subset. So every rectangle in *S* would have to be entirely to the right of *M*. So choose out *S* one rectangle that has the lowest bottom edge rectangles in *S*. Let's call it *P*. I will show that *P* has no rectangles entirely below it that it overlaps horizontally, so it should have been part of the initial subset, which contradicts our choice of *M* as the rightmost rectangle in that subset, thus showing that no such *P* exists and *S* is empty.

Clearly no rectangle in *S* is below *P* and overlaps *P* horizontally. What about the rectangles not in *S*? Suppose a rectangle *Q* is not in *S*, is entirely below *P* and overlaps *P* horizontally. The left edge of *Q* must be at or to the left of the left edge of *M*, otherwise *Q* would be in *S*. The right edge of *Q* must be to the right of the right edge of *M*, since *Q* overlaps *P* horizontally. So *Q* also overlaps *M* horizontally. The bottom edge of *Q* is below the bottom edge of *P* which is below the top edge of *M*, so *Q* must be entirely below *M* --- but this is impossible, since we chose *M* to have no rectangle overlapping horizontally below it.

Phew! That's not easy for something so "obvious".

This solution should make for a reasonably efficient algorithm.

- Sort the rectangles by right edge.
- Set R to the rightmost rectangle.
- If R has any rectangles overlapping horizontally below it, set R to the one of those rectangles with the rightmost right edge and go to step 3.
- Move R.
- Remove R from our list.
- If there are more rectangles in the list, go to step 2.

**Update** Actually I'm pretty sure you can do a direct proof of correctness of the above algorithm. At the beginning of step 3 you have the invariant that there are no rectangles to the right of the right edge of R and below the top edge of R. Using that invariant, I think you can construct a much simpler proof than the one I gave here.

Also, as at least one commenter observed, you can improve this algorithm by not throwing away all your work every time you go to step 2. That adds complexity though...

**Update** Fixed a typo in the answer to the first problem, pointed out by Boris.

## Comments

But it's pretty simple, to confirm what you got:

Any real square root must be positive, so assuming one solution is negative and one solution is positive then for some positive s, we can say:

(x + by +/- s)/(|p| - r^2)

Any as the assumption is that |p| < r^2 then the bottom would be some negative number, let's say -(1/u). We get

-(u)(x + by - s)

Or

-(u)(x + by + s)

So assuming x, b and y are positive then the first solution must hold. But I'm not convinced it's true for all p and q.

x + by < Sqrt(r^2 (x^2 + y^2) - (ay - bx)^2)

But I've not yet got a convincing proof for this inequality.

"If R has any rectangles overlapping horizontally below it, set R to the rectangle furthest down (highest Y value)."

Step 3 would also never be repeated then. You've already picked a rectangle with the rightmost edge, so the only thing that could go wrong is that there are multiple rectangles with that rightmost edge and you didn't pick the one furthest down.

Alternatively you can keep Step 3 as described and replace steps 1 and 2 with

"Pick an arbitrary rectangle in the set"

That seems to me like it would be more efficient because it eliminates the need to sort the 20, 50, 100, 500, or 5000 rectangles that aren't even remotely candidates to be the first rectangles to move.

1. Sort the rectangles by right edge.

2. If stack S is not empty, pop a rectangle off of S and set to R; else, set R to the rightmost rectangle.

3. If R has any rectangles overlapping horizontally below it, add R to the stack S, set R to the one of those rectangles with the rightmost right edge and go to step 3.

4. Move R.

5. Remove R from our list.

6. If there are more rectangles in the list, go to step 2.

Suppose you start with a single rectangle; obviously, that's free to move. Restricting to the "down and right" case, for every subsequent rectangle added, there will be a "down and rightmost" rectangle, which is free to be moved. Any rectangle added to block the down-and-rightmost free rectangle cannot be blocked by any previous rectangle, so there will always be a free rectangle. Finally, the connection between placing and moving rectangles: once a rectangle R is moved, any other rectangles that were blocked only by R are now free. Thus, (A) there will always be at least one free rectangle, and (B) every moved rectangle will leave at least one free unmoved rectangle.

This algorithm can be quite effictive, depending on the implementation details of building the DAG. If we have an API that supports the query "SELECT point from pointset if it is in convex_polygon", then the DAG is quite fast to build.

Over here, I get |ax + by| for that part, so I assume you just typo'd.

Still thinking about the rectangles thing; haven't read this part of the answers yet. ;)

|tp-q| = tr, |p|>r

Then |tp-q|^2 = t^2 r^2

Since |u-v|^2 = u.u +v.v -2u.v (you can verify this),

|tp|^2 +q.q -2tp.q = t^2 r^2 and

t^2 (p.p -r^2) -2tp.q +q.q = 0.

You can all write the quadratic solution from that.

VanillaMozilla: several people got that far, but as I said at the beginning of this post, you need to go a bit further and identify which solution to the quadratic equation is the right one.

First, as you note it's enough to find one rectangles to move and wlog we can assume the vector's components are nonnegative.

Now construct a directed graph with vertices corresponding to the rectangles, and an edge from vertex A to vertex B if B != A and B's bottom-right corner is below and to the right of A's top-left corner. That is, we have an edge from A to B if A+v (which is below and to the right of A) might possibly overlap B.

Next we prove the graph is acyclic, at which point any terminal vertex is safe to move. We can then keep track of the set of terminal vertices, throwing them out of the graph as we go. The problem here is that the initial graph construction is O(N^2) in number of rectangles... On the other hand, your step 3 is worst-case O(N), right? And we can probably optimize the graph-construction by sorting by left edge first or something along those lines.

Proof that the graph is acyclic. Assume otherwise, so that we have a cycle. Take a minimal-length cycle. If it is of length 2, so A -> B -> A, then the top edge of A is above the bottom edge of B but the top edge of B is above the bottom edge of A. So their projections onto the Y axis overlap. To be nonintersecting, they must be entirely to the left or right of each other (in the same sense as your "entirely above"/"entirely below"). But by the same argument we show their projections onto the X axis overlap. So we have a contradiction.

If the minimal cycle length is > 2, consider any three consecutive vertices A -> B -> C in the cycle. These must be distinct. Without loss of generality, we can assume that B is entirely below A (the other option is that it's entirely to the right of A). Now if C is entirely to the right of B, then in particular the bottom-right vertex of C is below and to the right of the the top-right vertex of B, which is by assumption below and to the right of the top-left vertex of A. Then our graph must have an edge A -> C, and we have a cycle one shorter than our original one, a contradiction. Hence the only remaining option is that C is entirely below B.

So we have shown that given any cycle, if we take three consecutive vertices A -> B -> C, either B is entirely below A and C entirely below B or B is entirely to the right of A and C entirely to the right of B. In the former case, we conclude that A is entirely to the right of A, a contradiction. In the latter case, A is entirely below A, also a contradiction.

General note: It feels pretty clear to me that this should be provable with convex shapes in general, not just rectangles. It also feels like my proof should be extendable to that situation, if one figures out how to correctly generalize the graph-construction part of things and concepts like "entirely below"... Then again, yours probably is too if one comes up with such a generalization.

VanillaMozilla: sorry about your text being lost, not sure what could have happened.

The line that passes through (3,7) and (r,4) has a slope of 4.

i have no idea what i doing here.