Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a discrete point set $S$ in ${\bf R}^2$ with a specified base-point $p_0 \in S$, label the remaining points as $p_1, p_2, \dots$ in order of increasing distance from $p_0$ (with ties resolved indifferently), and let $d_n(S,p_0)$ be the distance between $p_0$ and $p_n$.

What is known about the infimum of $d_n(S,p_0)$ as $S$ and $p_0$ vary, if $S$ is required to have the property that no two of its points are less than 1 apart? An equivalent statement of the problem replaces each point-set with a packing of the plane by disjoint disks of radius 1/2. It would be very nice if the infimum of $d_n$ was achieved by the hexagonal packing of the plane, but my intuition says that for some $n$ this is not the case; I wonder if this is known.

share|improve this question
Indeed, for n a hexagonal number, one needs a perturbed lattice, I think. Certainly d_7 can go below sqrt(3), and I suspect the infs for d_7 through d_12 will be equal. Gerhard "Ask Me About Perturbed Thinking" Paseman, 2012.12.13 –  Gerhard Paseman Dec 14 '12 at 3:56
In fact, one can use concentric arcs around p_0 to place the centers to get something like d_7 down to csc(2pi/7)/2, if I did the arithmetic correctly. Gerhard "Should Try Pencil And Paper" Paseman, 2012.12.13 –  Gerhard Paseman Dec 14 '12 at 4:03
Also some values might be related to packing circles in circles. The infimum won't be far from values computed there, e.g. at packomania.com. Gerhard "Not Affiliated With That Domain" Paseman, 2012.12.13 –  Gerhard Paseman Dec 14 '12 at 4:06
add comment

2 Answers

There's an intuitive way to see that $d_7$ is not achieved by the hexagonal packing: put five disks (evenly spaced), rather than six, around disk 0. Now add five disks into the gaps between the first five disks. It is easy to see that disks 6 through 10 in this packing are closer to the center than disk 7 in the hexagonal packing.

share|improve this answer
Henry Cohn writes: "Graham and Sloane conjecture that minimizing the second moment about the centroid leads to hexagonal lattice excerpts (except for 4 disks, where there's a one-parameter family of optima)." See R. L. Graham and N. J. A. Sloane, "Penny-packing and two-dimensional codes", Discrete Comput. Geom. 5:1-11 (1990) (math.ucsd.edu/~ronspubs/90_01_penny_packing.pdf) and T. Chow, "Penny-packings with minimal second moment", Combinatorica 15 (2) (1995) 151-158 ( This is not the question that I asked, but it's the question I should have asked! –  James Propp Dec 17 '12 at 16:38
add comment

Hopkins, Stillinger and Torquato give putative minima for $d_n$ for $n\le348$. In many cases these are improvements over a triangular lattice packing.

From the abstract:

The densest local packings of $N$ identical nonoverlapping spheres within a radius $R_\{min}(N)$ of a fixed central sphere of the same size are obtained using a nonlinear programming method operating in conjunction with a stochastic search of configuration space. The knowledge of $R_\{min}(N)$ in $d$-dimensional Euclidean space $R^d$ allows for the construction both of a realizability condition for pair-correlation functions of sphere packings and an upper bound on the maximal density of infinite sphere packings in $R^d$. In this paper, we focus on the two-dimensional circular disk problem. We find and present the putative densest packings and corresponding $R_\{min}(N)$ for selected values of $N$ up to $N=348$ and use this knowledge to construct such a realizability condition and an upper bound. We additionally analyze the properties and characteristics of the maximally dense packings, finding significant variability in their symmetries and contact networks, and that the vast majority differ substantially from the triangular lattice even for large N. Our work has implications for packaging problems, nucleation theory, and surface physics.

share|improve this answer
For me the paper is behind a aywall. Can you comment on the similarity between their data and data for certain circle in circle packings at packomania.com, specifically those N where the enclosing circle is concentric with a packed circle? Gerhard "Cookie Baking With Pizza Stones" Paseman, 2012.12.15 –  Gerhard Paseman Dec 15 '12 at 19:52
The paper also appears on the arXiv (arxiv.org/abs/1002.0604) and on Torquato's website (cherrypit.princeton.edu/papers/paper-292.pdf). –  Yoav Kallus Dec 15 '12 at 20:41
In cases where the optimal packing of circles in a circle yields a centered circles, the two numbers should match. I can't figure out how to identify those N's for which the former happens from the tables at packomania.com, so I can't check if this is true for the putative optima given by packomania.com and by Hopkins et al. –  Yoav Kallus Dec 15 '12 at 20:46
Thanks for the reference and redirect. Gerhard "Ask Me About System Design" Paseman, 2012.12.15 –  Gerhard Paseman Dec 15 '12 at 21:00
add comment

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.