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

The space of configurations of $k$ distinct points in the plane $$F(\mathbb{R}^2,k)=\lbrace(z_1,\ldots , z_k)\mid z_i\in \mathbb{R}^2, i\neq j\implies z_i\neq z_j\rbrace$$ is a well-studied object from several points of view. Paths in this space correspond to motions of a set of point particles moving around avoiding collisions, and its fundamental group is the pure braid group. It is not hard to prove that this space is homotopy equivalent to the configuration space of the unit disk $$F(D^2,k)=\lbrace(z_1,\ldots , z_k)\mid z_i\in D^2, i\neq j\implies z_i\neq z_j\rbrace$$

In real life however, particles, or any other objects which move around in some bounded domain without occupying the same space, have a positive radius, and so would be more realistically modelled by disks rather than points. This motivates the study of the spaces $$F(D^2,k;r)= \lbrace(z_1,\ldots , z_k)\mid z_i\in D^2, i\neq j\implies |z_i - z_j|>r\rbrace$$ where $r>0$. The homotopy type of this space is a function of $r$ and $k$. Fixing $k$ and varying $r$ gives a spectrum (is this the right word?) of homotopy types between $F(\mathbb{R}^2,k)$ and the empty space. It seems like an interesting (and difficult) problem to study the homotopy invariants as functions of $r$. For instance, for $k=3$ what is $\beta_1(r)$, the first Betti number of $F(D^2,k;r)$?

Question: Have these spaces and their homotopy invariants been studied before? If so, where?

Of course one can also ask the same question with disks of arbitrary dimensions.

share|improve this question
I wrote a detailed answer below including an example with hard disks in a square, but we also know some things about hard disks in a disk. Even though the boundary is smooth, things still get complicated pretty quickly. I have pictures of all the "critical configurations" we have found for disks in a disk, up to about seven disks, and I can email them on request. –  Matthew Kahle Mar 25 '11 at 21:32
Persi Diaconis mentioned a similar problem viewed from a slightly different perspective in his paper "The Markov chain Monte-Carlo revolution" –  Simon Lyons Mar 25 '11 at 21:54
My answer was going to be "Ask Matt Kahle," but since he's already answered, I'll just link to what I wrote about this problem on my blog: in particular, its conceptual affinity with the "15 puzzle." quomodocumque.wordpress.com/2009/04/04/… –  JSE Mar 26 '11 at 20:41

3 Answers 3

up vote 24 down vote accepted

I have a number of results on hard disks in various types of regions, and preprints are in progress. The terminology "hard spheres" (or "hard disks" in dimension 2) comes from statistical mechanics, and I believe Fred Cohen is following my lead on this. (See for example the hard disks section of Persi Diaconis' survey article.)

--- With Gunnar Carlsson and Jackson Gorham, we did numerical experiments and computed the number of path components for 5 disks in a box, as the radius varies over all possible values. This is quite a complicated story already, as the number is not monotone or even unimodal in the radius. (This preprint is almost done, a rough copy is available on request.)

--- With Yuliy Baryshnikov and Peter Bubenik we develop a general Morse-theoretic framework and proved that in a square, if $r < 1/2n$ then the configuration space of $n$ disks of radius $r$ is homotopy equivalent to $n$ points in the plane. On the other hand this is tight: if $r> 1/2n$ then the natural inclusion map is not a homotopy equivalence. (Again this preprint is getting close to be being posted to the arXiv...) There is a much more general statement here.

--- I also have some results with Bob MacPherson about hard disks in a square and also in (the easier case of) an infinite strip. We have been talking to Fred Cohen about this a bit lately, who believes there may be connections to more classical configuration spaces.

I am slightly self-conscious about claiming results here, without first having posted the preprints to the arXiv, but I just wanted to state that there are a number of things known now, and I am working hard to get everything written up in a timely fashion. In the meantime I have some slides up from a talk I recently gave at UPenn.

Here is a concrete example, since that might be more satisfying.

It turns out for $3$ disks in a unit square:

For $0.25433 < r$, the configuration space is empty,

for $0.25000 < r < 0.25433$ it is homotopy equivalent to $24$ points,

for $ 0.20711 < r < 0.25000$ it is homotopy equivalent to $2$ circles,

for $ 0.16667 < r < 0.20711 $ it is homotopy equivalent to a wedge of $13$ circles, and

for $ r < 0.16667$ it is homotopy equivalent to the configuration space of $3$ points in the plane.

For $4$ disks in a square it looks like the topology changes $9$ or $10$ times, and for $5$ disks it looks like the topology might change $25$-$30$ times or more. The general idea is that certain types of "jammed" configurations act like critical points of a Morse function, and mark the only places where the topology can chance.

Update: two preprints have been posted to the arXiv.

Min-type Morse theory for configuration spaces of hard spheres (w/ Baryshnikov and Bubenik):

Computational topology for configuration spaces of hard disks (w/ Carlsson, Gorham, and Mason): http://arxiv.org/abs/1108.5719

share|improve this answer
Thankyou for your nice answer and for linking to the slides. Now I remember hearing Baryshnikov talk about this (my visual memory was sparked by your picture of "Kahle's corner"). So is it correct to say: (1) that these jammed configurations can't occur for disks in a disk or squares in a square; (2) that the models in (1) are equivalent, and harder than disks in a square? –  Mark Grant Mar 26 '11 at 8:05
Nice answer. I think that squares in squares is easier than discs in a square, I'd very much like to know where discs in discs lies, is it harder than squares in squares (I'd imagine so). Is it only easier than discs in squares because it has the full orthogonal symmetry, rather than the dihedral symmetry? Finally, a fun application is to origami. Circle packings in squares give optimum folds of animals with a fixed number of 'legs'. See Lang's Origami Design Secrets. –  James Griffin Mar 26 '11 at 12:52
@ Mark, James: I think squares in a region is generally easier than disks in a region, at least if we assume that the sides stay parallel to the axes. From a lot of experimenting with small examples I believe that disks in a disk looks slightly easier than disks in a square at first, but that this is a little misleading --- it only takes a few more disks for the complications to begin. For example: with 3 disks in a disk, the topology only changes twice. But by the time you get up to 7 disks in a disk, it looks like the topology changes at least 18 times as the radius varies. –  Matthew Kahle Mar 26 '11 at 13:26
A related question: do more inequivalent configurations occur if the disks can have varying radii? –  Brendan McKay Aug 30 '11 at 3:28

Yes, there has been a lot of work by Fred Cohen (University of Rochester, currently at IAS) on the subject. He has been giving talks about this (he calls it the hard sphere model), but I can't seem to find a relevant paper/preprint. Perhaps you can contact him directly. EDIT I have somehow managed to confuse Cohen's work and Matt Kahle's (if you know them both, you know how impressive a feat that is). Matt's answer is the true received wisdom.

share|improve this answer

I would very much appreciate a good answer to this question, perhaps a follow up to Igor's answer as this is something that I have thought about before, but have not come across in the literature.

I quickly (perhaps too quickly) abandoned the discs model in favour of the little cubes model, or perhaps I should say the hard cubes model.

For hard 2-cubes and k=3 I think the homology groups are:

for r > 1/2: clearly 0

for 1/2 >= r > 1/3: H_0 = Z^6, H_1=Z^6 and H_i=0 for i>1

the three squares are effectively arranged in a circle which can be rotated, the order (and not just the cyclic order!) parametrises the 6 connected components.

for 1/3 >= r we get the usual configuration space: H_0 = Z, H_1 = Z^3, H_2 = Z^2 and H_i=0 for i>2.

share|improve this answer

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.