|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 co-authored 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 k-1 and k+1. It is easy to see that order n3 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 non-constructive 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 non-constructive methods - I know which one I find more attractive...
|Last Updated ( Sunday, 24 April 2011 )|