Eyes Above The Waves

Robert O'Callahan. Christian. Repatriate Kiwi. Hacker.

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 = (ax + by - √(r²(x² + y²) - (ay - bx)²))/(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.

  1. Sort the rectangles by right edge.
  2. Set R to the rightmost rectangle.
  3. 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.
  4. Move R.
  5. Remove R from our list.
  6. 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.


Neil Rashbrook (without a trailing e!)
No blame to Wolfram Alpha for this, it actually gave me all possible roots including imaginary ones, and I couldn't work out how to a) ask it for positive real roots only or b) specify that r² > a² + b², so I just picked the one that I thought was positive real; I'd have written (r² - a² - b²) if I'd noticed that (a² + b² - r²) was negative.
Ahh yes, I hadn't spent the time to calculate which was the positive answer.
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)
-(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.
Nope, playing around with a bit further, I think you're always correct about the choice of sign. Because The nominator is always negative because
x + by < Sqrt(r^2 (x^2 + y^2) - (ay - bx)^2)
But I've not yet got a convincing proof for this inequality.
Kyle Huey
Your proof looks good to me. The algorithm seems a bit odd though. If you sort the rectangles ahead of time by right edge then in step 3 should be
"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.
Kyle Huey
On the other hand it might be better to sort the rectangles ahead of time, because you would have to iterate every time through and sort just once.
Michael Ryan
Going back to step 2 would be pretty inefficient in the worst case. I think this would work better:
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.
Ben Karel
Wouldn't a somewhat simpler proof for #2 to be by contradiction, by proving that it's impossible to construct an arrangement that doesn't have a valid "undoing" sequence? I think that this approach captures the intuitive way of thinking about the problem.
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.
Robert O'Callahan
That might work, but I think you need to formalize it more ... I'm not sure what you mean by "down and rightmost", for example.
Daniel Varga
To me the most intuitive algorithm to the rectangles problem is the following. Define a directed acyclic graph on the rectangles: Rectangle A is connected to rectangle B if moving rectangle A in the direction of v it eventually hits rectangle B. (Several commenters noted that this graph is indeed acyclic.) Any topological ordering of this DAG will be a solution to the original problem.
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.
Neil Rashbrook
Informally, I was trying to work out how far I could generalise the question, and realised that the back-to-front 3D rendering algorithm is another special case of using a vector to provide a strict partial ordering over a series of convex objects. I think all that is left to prove is that the dependency graph is acyclic (I have already proved that it is directed).
Your formula for t can't possibly be right, since |x + by| is clearly bogus (units mismatch!).
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. ;)
I know I'm late to this, but it's worth commenting on the vector approach because it's so powerful and compact. Sjoerd Visscher did this, but for some reason changed the variables. Here's my approach, which may be a little simpler.
|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.
Robert O'Callahan
Boris: yes, it's a typo, will fix...
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.
Robert O'Callahan
VanillaMozilla: I like the vector approach though.
Well, for that matter I didn't give the solution either, since the emphasis was on the vector method. As you pointed out, if t>0 and |p|r, a solution does not necessarily exist. Of course you knew that.)
My last comment appears nonsensical after the first sentence because it is only part of what I posted. There is a large chunk of text missing from the middle.
OK, so as far as the rectangles problem goes, here's what I ended up coming up with, in brief. It's an existence proof; not sure how fast the resulting algorithm would be.
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.
Robert O'Callahan
That's a nice proof!
VanillaMozilla: sorry about your text being lost, not sure what could have happened.
can anyone help me with the following problem:
The line that passes through (3,7) and (r,4) has a slope of 4.
i have no idea what i doing here.