MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Imagine I perform a random sequential adsorption (RSA) simulation for circles or discs of some radius $r \leq 1$ in $[0, 1]^2$ (I am open to changing this geometry to the unit circle). As a function of $r$, what is the best known lowerbound for the number of discs I can place on the surface s.t. all discs are guaranteed to fit? In other words, if I simulate RSA until I place all $N$ discs on the bounded surface, for some value of $r$, what is the largest known $N$ s.t. my simulation guaranteed to halt?

share|cite|improve this question
up vote 1 down vote accepted

If you can't fit another disc with radius $r$ in, then it means that every point is within $2r$ of one of the current centers. So, you are asking how efficient a covering by discs can be. Asymptotically, the most efficient covering is the hexagonal one, with efficiency $\frac{3\sqrt{3}}{2\pi}$. So, in a square or disc of area $A$, you can place at least $A/((6\sqrt{3} + o(1)) r^2)$ discs of radius $r$. The geometry of the region doesn't affect the asymptotics, but you can't simultaneously let the region vary as $r$ does, or that would allow you to consider a union of discs of radius $2r$, which can be covered by discs of radius $2r$ with perfect efficiency.

share|cite|improve this answer
@DouglasZare I'm not really asking how efficient the packing can be. I'm asking, given that the circles are placed on the surface randomly, what value of $N$ can strictly be achieved without jamming. – FloatingLantern Apr 13 '13 at 5:34
@FloatingLantern: Covering by discs of radius $2r$ is the same thing as being unable to place a disc of radius $r$. – Douglas Zare Apr 13 '13 at 7:22
@DouglasZare Oh, I'm sorry I sloppily misread your posting. – FloatingLantern Apr 13 '13 at 7:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.