# Maximum overhang

@article{Paterson2008MaximumO, title={Maximum overhang}, author={Mike Paterson and Yuval Peres and Mikkel Thorup and Peter Winkler and Uri Zwick}, journal={The American Mathematical Monthly}, year={2008}, volume={116}, pages={763 - 787} }

How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. However, at SODA'06, Paterson and Zwick constructed n-block stacks with overhangs of order n1/3. Here we complete the solution to the overhang problem, and answer Paterson and Zwick's primary open question, by showing that order n1/3 is best possible. At the heart of the argument is a… Expand

#### Topics from this paper

#### Paper Mentions

#### 16 Citations

Reviews

- 2017

Most of the time we think of a puzzle as an abstract but static thing, namely, a question that requires a clever answer. But puzzles evolve over time, sometimes splitting (like a living organism)… Expand

Further Thoughts on a Paradoxical Tower

- Mathematics, Computer Science
- Am. Math. Mon.
- 2018

First, a set of blocks of variable width are stacked so that there is one block at each level, and it is described how they should be stacked to maximize their overhang. Expand

Collapse

- Computer Science
- SODA '11
- 2011

Gauß' principle of least restraint is used to show that rigid-body simulation problems in which many parts touch each other can be reduced to solving a sequence of convex quadratic programs, with linear constraints, corresponding to a discretization of time. Expand

Optimal Control for Diffusions on Graphs

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2018

This work investigates the minimum number of controlled diffusion steps needed to transport a constant mass $p$ outside of the ball of radius $n$ and considers graphs where simple random walk has positive speed and entropy and which satisfy Shannon's theorem. Expand

Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading

- Computer Science, Mathematics
- LATIN
- 2018

This work considers dynamic loading and unloading problems for heavy geometric objects and gives optimal approaches for several variants that model different loading scenarios that may arise, e.g., in the loading of a transport ship with containers. Expand

Meteor process on $${\mathbb Z}^d$$Zd

- Mathematics
- 2015

The meteor process is a model for mass redistribution on a graph. The case of finite graphs was analyzed in Billey et al. (On meteors, earthworms and WIMPs. Ann Appl Probab, 2014). This paper is… Expand

Profile of Yuval Peres

- Sociology, Medicine
- Proceedings of the National Academy of Sciences
- 2018

During a distinguished career, Peres has continued to work on probability and ergodic theory and has tackled numerous other topics, including fractals, random walks, Brownian motion, game theory, and information theory. Expand

Meteor process on ${\mathbb Z}^d$

- Mathematics
- 2013

The meteor process is a model for mass redistribution on a graph. The case of finite graphs was analyzed in \cite{BBPS}. This paper is devoted to the meteor process on ${\mathbb Z}^d$. The process is… Expand

A Formal Framework for Robot Construction Problems: A Hybrid Planning Approach

- Computer Science
- ArXiv
- 2019

A formal hybrid planning framework to solve a wide range of robot construction problems, based on Answer Set Programming is proposed, which not only decides for a stable final configuration of the structure, but also computes the order of manipulation tasks for multiple autonomous robots to build the structure from an initial configuration. Expand

Efficient Algorithms and Data Structures

- Computer Science
- 2012

The proposed project will address some of the fundamental issues in effi c ent algorithms and data structures, ranging from pseudo-random hashing, to the existenc e of deterministic dictionaries with… Expand

#### References

SHOWING 1-10 OF 60 REFERENCES

Preliminary Version

- 1994

The main theorem of this paper is that, for every real number < 1 (e.g., = 0:99), only a measure 0 subset of the languages decidable in exponential time are Pn tt-reducible to languages that are not… Expand

Fun with stacking blocks

- Physics
- 2005

How can a given number of rigid, rectangular blocks be stacked in a planar arrangement to produce the maximum overhang over a support edge? To answer this question, three cases of increasing… Expand

Overhang

- Mathematics, Physics
- SODA '06
- 2006

It is shown that the stability of a given stack of blocks corresponds to the feasibility of a <i>linear program</i> and so can be efficiently determined. Expand

American Mathematical Monthly

- 2010

s for articles or notes should entice the prospective reader into exploring the subject of the paper and should make it clear to the reader why this paper is interesting and important. The abstract… Expand

Theory of linear and integer programming

- Mathematics, Computer Science
- Wiley-Interscience series in discrete mathematics and optimization
- 1999

Introduction and Preliminaries. Problems, Algorithms, and Complexity. LINEAR ALGEBRA. Linear Algebra and Complexity. LATTICES AND LINEAR DIOPHANTINE EQUATIONS. Theory of Lattices and Linear… Expand

Sixth book of mathematical games from Scientific American

- History, Computer Science
- 1971

Both the size and quantity of crystal particles removed from the slurry body are independently regulated, thereby providing product crystals of improved size uniformity. Expand

Mad about physics : braintwisters, paradoxes, and curiosities

- Engineering, Physics
- 2001

Temperature Risin'. Color My World. Splish! Splash! Fly like an Eagle. Good Vibrations. Opposites Attract. Bodies in Motion. Stairway to Heaven. Life in the Fast Lane. Born to Run. Third Stone from… Expand

Mad About Physics: Braintwisters

- Paradoxes, and Curiosities, John Wiley, New York
- 2001

A Collection of Problems in Illustration of the Principles of Theoretical Mechanics

- Computer Science
- 2009

Puzzle-Math, Viking, New York, 1958

- January
- 2009