Sunday, 23 August 2009


I'm back in Auckland for one night before I head off again to California. The Australia trip was great. We roamed around Sydney visiting friends and relatives, but had a couple of days in the Blue Mountains on our own. The weather was great throughout. I achieved complete Internet independence for a week, no withdrawal symptoms.

Like most of our trips there was lots of walking and lots of eating. The Blue Mountains were excellent --- great views, and really interesting geology and habitats, especially the way water trickles down the cliffs forming amazing "hanging swamps". We loved the Wentworth Falls area, especially the National Pass walk that descends from the top of the escarpment down through wet gullies and then along a shale ledge halfway up great Triassic sandstone cliffs, then up hundreds of steep steps beside the waterfall. The track's graded "hard", probably due to the staircases, and the nominal time is 3 to 4 hours, but we did it in 2:45 including lots of lookout stops ... not bad for my 4 year old son! We'd already walked 2.5 hours down the Giant Staircase and along Dardanelle Pass in Katoomba that morning. The following day we walked to the bottom of Govett's Leap falls and back up, also very nice, but a bit trickier due to wet rock surfaces, especially going down.

If I'd realized before booking how much of the appeal of the Blue Mountains rests on peering over precipices and descending impossibly steep stairs, I might have had second thoughts on account of my fear of heights. Since I had a great time anyway, I'm glad I didn't know!

Just before these walks I'd been reading The Watchmen (fabulous). I was struck by the contrast between that bleak vision of fallen humanity and the glorious beauty of God's creation. It's good to look away from man for a while.

Movie roundup:

  • JJ Abrams' Star Trek: pretty good
  • X-Men Origins: Wolverine: better than expected, which isn't saying much
  • Shaolin Temple (1982): Jet Li's first major role. Otherwise not very interesting except that there are some astounding apparently real action sequences, where for example a man does handsprings without hands, just flipping over onto his head and then back up again.
  • Roman Holiday: Even better than I remembered, definitely a must-see
  • Anna and the King: How can you put two of my favourite actors, Jodie Foster and Chow Yun-Fat, in starring roles and make such a terrible movie? I don't know, but it's not worth watching to try to find out. Upsetting.

Friday, 14 August 2009

On The Road

From mid-tomorrow until August 22 I'm going to be on holiday in Australia. I'm not bringing my laptop --- I'll be completely offline --- so don't expect me to reply to anything.

From August 23 to 28 I'll be in California for Mozilla meetings. I'll be online during much of that time.

Monday, 10 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.

Winter's Day On The West Coast

On Saturday our family went out to the west coast with Mozilla intern Markus Stange and another friend, to enjoy a fine winter's day, get some exercise, and show off some of the spectacular scenery of the Waitakere coast.

We started at the end of Te Ahuahu Road just south of Piha. The Mercer Bay Track started with instant gratification of views over Piha and the Tasman Sea and then took us south down the hill to a lookout over towering cliffs, where we had lunch. We carried on south to the Ahu Ahu Track and then Comans Track, which winds south and downhill to Karekare, with great views north to Mercer Bay and south over Karekare Beach to Whatipu along the way. The tracks were muddy in places but otherwise in good shape.

At Karekare we walked on the beach for a while and checked out the rocks and pools at the north end of the beach. Markus distinguished himself with some inspiring rock climbing. There were some good waves rolling in, and an easterly wind was blowing the tops off the waves --- spectacular.

My wife had brought the car down, so we drove back to Piha and headed to the end of Glen Esk Road for the track to Kitekite Falls. It's an easy gravel track beside the Kitekite Stream, very relaxing. The return leg has a couple of easy stream crossings. The Falls always look great.

Then we headed back to Piha beach and wandered to the southern end. Markus and I took a quick walk further south along the Tasman Lookout track and found a way down the hill to the beach behind the small Taitomo Island, which is connected to the mainland by sand which is only covered at high tide. The way down the rock face wasn't easy to find though! We stood near "The Gap" in the island watching waves crash through the narrow passage between two parts of the island; we were surprised by a particularly big surge which flooded the area all around us, leaving us on an isolated dry spot! No wonder so many rock fishing people drown. We got away dry and walked back to Piha beach around the rocks.

After all that we had one more walk: up Lion Rock in the middle of the beach. It's steep, but easy, and a great view. Too bad you can only go halfway up these days due to instability at the summit. The sun set behind clouds over the ocean.

Altogether we were in the area from about 11:30am to 5:30pm --- a superb day. (I solved homework problem #2 somewhere along the way, too!) My kids were still running around at the end, so I'm going to have to upgrade the difficulty of these trips!

We finished the day by driving back to the city and having dinner at Sunshine. As far as I know it's still the best Chinese restaurant in Auckland, as good as I've had anywhere in Australasia and North America. And though it's not the cheapest place in town, it's not really expensive either; last night's dinner was $84 for the set menu for six.

All in all I have to thank God for letting me live here :-).

View over Mercer Bay from Comans Track

View over Karekare to Whatipu from Comans Track

View of 'The Gap' from Tasman Lookout Track

Sunset at Piha

Saturday, 8 August 2009


Two interesting problems I've had to solve this week...

Given a point p and a radius r, consider the family of circles Ct, where t is a positive real number, with centres tp and radii tr. Given a point q, find the smallest value of t such that the circle Ct contains q. You may assume |p| < r. This came up while I was optimizing repeating radial gradients for Mac.

Given a set of non-overlapping axis-aligned rectangles in the plane, and a 2D vector v, order the rectangles in a sequence so that translating each rectangle one by one by v does not have any overlapping rectangles in the intermediate states. Does such an order always exist? This came up while I worked on optimizing scrolling.