tag:blogger.com,1999:blog-71141318914133781.post2507098216004324655..comments2020-09-28T08:15:48.552+13:00Comments on Eyes Above The Waves: Homework AnswersRoberthttp://www.blogger.com/profile/01801341049800948737noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-71141318914133781.post-13034334792848308022010-12-02T20:32:36.000+13:002010-12-02T20:32:36.000+13:00can anyone help me with the following problem:The ...can anyone help me with the following problem:<br>The line that passes through (3,7) and (r,4) has a slope of 4.<br>i have no idea what i doing here.<br>andreanoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-88452646164519265852009-08-13T03:49:28.000+12:002009-08-13T03:49:28.000+12:00That's a nice proof!VanillaMozilla: sorry abou...That's a nice proof!<br>VanillaMozilla: sorry about your text being lost, not sure what could have happened.<br>Robert O'Callahannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-87347808008186749542009-08-13T03:27:19.000+12:002009-08-13T03:27:19.000+12:00OK, so as far as the rectangles problem goes, here...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.<br>First, as you note it's enough to find one rectangles to move and wlog we can assume the vector's components are nonnegative.<br>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.<br>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.<br>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.<br>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.<br>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.<br>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.<br>Borisnoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-62598617681555946822009-08-12T14:12:09.000+12:002009-08-12T14:12:09.000+12:00My last comment appears nonsensical after the firs...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.<br>VanillaMozillanoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-55602544038774260422009-08-12T04:21:16.000+12:002009-08-12T04:21:16.000+12:00Well, for that matter I didn't give the soluti...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.)<br>VanillaMozillanoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-8478640527426757282009-08-11T22:54:33.000+12:002009-08-11T22:54:33.000+12:00VanillaMozilla: I like the vector approach though....VanillaMozilla: I like the vector approach though.<br>Robert O'Callahannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-21702345732137500802009-08-11T22:51:06.000+12:002009-08-11T22:51:06.000+12:00Boris: yes, it's a typo, will fix...VanillaMoz...Boris: yes, it's a typo, will fix...<br>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.<br>Robert O'Callahannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-63169743463407596062009-08-11T18:36:12.000+12:002009-08-11T18:36:12.000+12:00I know I'm late to this, but it's worth co...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.<br>|tp-q| = tr, |p|>r<br>Then |tp-q|^2 = t^2 r^2<br>Since |u-v|^2 = u.u +v.v -2u.v (you can verify this),<br>|tp|^2 +q.q -2tp.q = t^2 r^2 and<br>t^2 (p.p -r^2) -2tp.q +q.q = 0.<br>You can all write the quadratic solution from that.<br>VanillaMozillanoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-21341925269735841792009-08-11T15:37:56.000+12:002009-08-11T15:37:56.000+12:00Your formula for t can't possibly be right, si...Your formula for t can't possibly be right, since |x + by| is clearly bogus (units mismatch!).<br>Over here, I get |ax + by| for that part, so I assume you just typo'd.<br>Still thinking about the rectangles thing; haven't read this part of the answers yet. ;)<br>Borisnoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-20667675443410695472009-08-11T11:52:58.000+12:002009-08-11T11:52:58.000+12:00Informally, I was trying to work out how far I cou...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).<br>Neil Rashbrookhttp://neil.rashbrook.org/noreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-54526270027001687842009-08-11T11:51:04.000+12:002009-08-11T11:51:04.000+12:00To me the most intuitive algorithm to the rectangl...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.<br>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.<br>Daniel Varganoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-79617778429489368992009-08-11T05:55:32.000+12:002009-08-11T05:55:32.000+12:00That might work, but I think you need to formalize...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.<br>Robert O'Callahannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-59811387295621959402009-08-11T05:50:53.000+12:002009-08-11T05:50:53.000+12:00Wouldn't a somewhat simpler proof for #2 to be...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.<br>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.<br>Ben Karelhttp://eschew.orgnoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-72189428546918175852009-08-10T15:09:32.000+12:002009-08-10T15:09:32.000+12:00Going back to step 2 would be pretty inefficient i...Going back to step 2 would be pretty inefficient in the worst case. I think this would work better:<br>1. Sort the rectangles by right edge.<br>2. If stack S is not empty, pop a rectangle off of S and set to R; else, set R to the rightmost rectangle.<br>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.<br>4. Move R.<br>5. Remove R from our list.<br>6. If there are more rectangles in the list, go to step 2.<br>Michael Ryannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-75498993508057715142009-08-10T15:09:05.000+12:002009-08-10T15:09:05.000+12:00On the other hand it might be better to sort the r...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.<br>Kyle Hueynoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-87629522745770670912009-08-10T15:05:40.000+12:002009-08-10T15:05:40.000+12:00Your proof looks good to me. The algorithm seems ...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<br>"If R has any rectangles overlapping horizontally below it, set R to the rectangle furthest down (highest Y value)."<br>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.<br>Alternatively you can keep Step 3 as described and replace steps 1 and 2 with<br>"Pick an arbitrary rectangle in the set"<br>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.<br>Kyle Hueynoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-25404786698326238782009-08-10T14:08:02.000+12:002009-08-10T14:08:02.000+12:00Nope, playing around with a bit further, I think y...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<br>x + by < Sqrt(r^2 (x^2 + y^2) - (ay - bx)^2)<br>But I've not yet got a convincing proof for this inequality.<br>Damiannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-17174346559251902062009-08-10T13:28:47.000+12:002009-08-10T13:28:47.000+12:00Ahh yes, I hadn't spent the time to calculate ...Ahh yes, I hadn't spent the time to calculate which was the positive answer.<br>But it's pretty simple, to confirm what you got:<br>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:<br>(x + by +/- s)/(|p| - r^2)<br>Any as the assumption is that |p| < r^2 then the bottom would be some negative number, let's say -(1/u). We get<br>-(u)(x + by - s)<br>Or<br>-(u)(x + by + s)<br>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.<br>Damiannoreply@blogger.comtag:blogger.com,1999:blog-71141318914133781.post-11085636529794303552009-08-10T12:45:35.000+12:002009-08-10T12:45:35.000+12:00No blame to Wolfram Alpha for this, it actually ga...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.<br>Neil Rashbrook (without a trailing e!)http://neil.rashbrook.org/noreply@blogger.com