I considered such possibilities, but ruled them out. (But remember, I also said your "tree" approach wouldn't work ;-)

My approach works cleanly and easily for 2D, but it relies heavily on the fact that it's 2D -- I can't imagine a parallel approach working in 3D (which hasn't stopped me from trying!). It seems to me that your post with the spoiler included holds the answer. Just have to figure out how to apply it to this problem.