The maximum overhang algorithm 
Written by Alex Armstrong 
Sunday, 24 April 2011 
From playing with bricks as small children we all understand the idea of overhang  or at least we used to think we did. Award winning research suggests there is more to it. Â It is nice to know that Microsoft Research gets up to other things than just inventing whole body sensors like Kinect. Recently the Theory Group has won the David P. Robbins Prize from the Mathematical Association of America  it may not be the Fields Medal but the work is fascinating if you have any interest in solving problems. This particular problem is called the Maximum Overhang problem and it has been considered as solved for a very long time  until a member of the Theory group coauthored a paper called "Maximum Overhang"  which also might be a good name for a rock group. The problem is very simple to state. All you have to do is take some bricks (books will do as long as they are not the electronic kind) and create a stack with the biggest overhang for that number of bricks. If you try it you quickly get the reason why it is a tricky problem. Making the books overhang slightly produces more stability but little overhang, whereas pushing bricks further out produces more overhang but the column becomes unstable more quickly. You might also conclude that you can create an overhang of more than one block  but you cannot. The solution is to take the n bricks and space them so that each one overlaps by 1/(2B) where B is the number of the brick (starting at the top): Â Â This creates a stack of bricks that overhangs by 1/2logn. As the series 1/n is the harmonic series this is called the harmonic stack and it was thought to be the best overhang you could achieve with just n bricks. Also notice that as the harmonic series diverges you can create an overhang of any size given enough bricks. The harmonic stack is an elegant solution so it comes as a surprise to learn that you can do better by creating stacks that resemble a badly build wall. What the solution needs are holes, jagged edges and specific counterweights. Using a computer search, optimal stacks of size n=20 and n=20 were found: Optimal stack for n=20 compared to harmonic stack Â Optimal stack for n=30 compared to harmonic stack Â To solve the problem completely however what you need is an upperbound on the overhang as a function of n  clearly the n=20 and n=30 results mean that it can't be the classical harmonic log n bound. The question is solved by first setting up a model for what a balanced stack of n bricks has to satisfy in terms of forces and showing that the overhang has to be less then 6n^1/3. This is done by noting that the distribution of forces needed for a balanced stack is the same as the mass movement problem  how many moves does it take to shift an initial mass distribution so that a given proportion is moved beyond a given distance. It turns out that it is easier to put bounds on this problem than the overhang problem and this gives the result that the overhang can be at most 6n^(1/3). "Starting with a unit of mass at the origin, how many moves does it take to move half the mass to distance n, where in each move a node k between n and n is chosen and the mass at k is split evenly between k1 and k+1. It is easy to see that order n^{3} moves suffice, and a key step of the Maximum Overhang paper was to show that this number of moves is also necessary." Notice that this is an upper bound and there is no evidence that it can be achieved  this is what nonconstructive math is often like! Currently the largest overhang actually achieved is 0.57n^(1/3) using a "brick wall stack" with a roughly parabolic shape: A "6 stack" n=111 with an overhang of 3 Â We still don't have a tight upper bound on what overhang can be achieved. You could push forward the subject by finding stable stacks that get closer to the upper bound or by proving it using nonconstructive methods  I know which one I find more attractive...More informationÂ

Last Updated ( Sunday, 24 April 2011 ) 