Thread: Loosest circle packing

First, a description of what I'm talking about: given a finite metric space, what is the minimum number of non-overlapping circles of a given radius that can cover the area so that no other circles can be added?

I suppose my main question is, is this a known, named problem? If so, what is it usually called?

Also, is this the same problem as asking how few overlapping circles can cover the whole space?

Sounds like the sphere-packing problem to me.

It sounds like the opposite of sphere packing--he's trying to get the worst packing, not the best.

Right. Bascially, if you knew the answer, then you'd know that if you picked random, non-overlapping circles in the space you'd be guaranteed to get at least so many.

If you don't put conditions on your metric space, you can come up with examples where there is no minimum for some interval of radii. For example, if you take the set C[[X]], the set of power series with complex coefficients, you can define a metric by letting:

d(f(X),g(X)) = 2^-k

where k is the power on X of the first nonzero term in the power series f(X)-g(X) (and, if f(X) = g(X), f(f(X),g(X)) = 0). Then, for any radius r < 1 and any finite collection of balls of radius r, you can find another ball of radius r with trivial intersection with the collection. For example, if we take, say, r = 0.5, then note that d(f(X),g(X)) ≤ 0.5 f(0) = g(0), i.e. f(X) and g(X) have the same constant coefficient. So the closed balls of radius 0.5 are power series which have the same constant coefficient. And any complex number can be a constant coefficient. So there is an infinite set of disjoint, mutually exhaustive closed balls of radius 0.5.

If you assume you're working on a nicer space, say a compact manifold, then you can probably come up with some nontrivial answers. Try seeing what you can say for the 2-sphere and the torus. At first I thought this would be real easy, but it looks quite interesting.

After thinking about your comment a bit, I've gotten myself confused about the definition of a finite metric metric space. Is your example finite? Well, the space I was originally thinking about was RGB color space and picking visually distinct random colors.

I was imagining finite to mean finite diameter, i.e. there exists some R > 0 such that d(x,y) < R for all elements x and y in your space. All of my examples satisfy this. But what do you mean? Do you mean a finite set?

Finite diameter should work too, since there should be an anwser to this for Euclidean spaces. Any finite set would have a finite diameter, right? Well, for a finite set, there'd always be a finite answer, but for some infinite sets of finite radius (like your example) there isn't. So, I wonder what conditions a set would have to satisfy to have a finite answer to this question.

I think the property we're looking for is total boundedness. A metric space is totally bounded if it can be covered by a finite number of balls of radius r for any r > 0. Let's call the property we're interested in P--i.e., a metric space X satisfies P if, given any r > 0, there exist finitely many disjoint balls of radius r such that any ball of radius r intersects at least one of these balls nontrivially. Then I claim P and total boundedness are equivalent. It's clear that not P implies not totally bounded.

The other way is less trivial but pretty easy. Let X be a metric space satisfying P, and let r > 0. We want to cover X by balls of radius r. Well, apply P for r/2, say with balls B(r/2,x₁), ..., B(r/2,x_k). So, for any y in X, there must exist some i such that B(r/2,x_i) and B(r/2,y) have nontrivial intersection, say the point z lies in their intersection. But then d(x_i,y) ≤ d(x_i,z) + d(z,y) < r. So you can cover X by the balls B(r,x_i), and X is totally bounded.

So we should restrict our attention to totally bounded spaces.

Isn’t that the same as saying that the space is compact?

Compactness requires completeness, too. That's the Heine-Borel theorem.

++++++++++++

Edit: a fun example! Let p be a prime, and consider the integers with respect to the p-adic metric. First, for an integer n, define the p-adic absolute value as such:

-If n = 0, |0|_p = 0.
-If n = p^kr, (p,r) = 1, k ≥ 0, then |n|_p = p^-k

Now define the p-adic metric:

d(x,y) = |x-y|_p

[Fun fact: the p-adic metric satisfies the "strong" triangle inequality, or the ultrametric inequality--for any x, y, and z, we have d(x,y) ≤ max{d(x,z), d(y,z)}.]

You can check that the open balls are precisely the cosets of the ideals of the form p^kZ, and so clearly this space is totally bounded.

Now define a system of open sets as follows:

-Let U₁ = pZ.
-Let U₂ = 1+p²Z.
-In general, let U_n = x_n+pⁿZ, where |x_n| (usual absolute value here) is minimal among integers not in any of the U_k for k < n.

You can check that these sets are disjoint, and it's clear from the construction that we eventually cover all integers. And since this is an infinite disjoint union, it can't have a finite subcover!

A fascinating problem.

It is not possible to cover an area with non-overlapping circles, simply because the circle does not tile any space. The term 'covering' in mathematics refers to a complete covering of a space (no gaps).
If instead you meant the least dense arrangement of circles of a given radius that do not allow additional circles to be placed, then in 2D the answer is a pattern in which the circle centers belong to the hexagonal lattice (also called equilateral triangular lattice). Just make sure that the distance between each circle is 2*sqrt(3)-epsilon the radius of each circle. This will give you a packing density of about 30%. For higher dimensions the solution is not currently known.

This is what happens in the bulk (or for non-finite spaces), if you have a finite space then you also need to take into account the boundary effect, which in general will generate a local distortion of the lattice above.

Regarding the name of the problem, surely it is not a 'packing' problem. Packing problems deal with spheres (or circles) that touch each other. As far as I know, the problem has no given name, but it could coincide with either the packing-covering problem or the quantizing problem (see N. J. Sloane and J. H. Conway's book 'Sphere Packings, Lattices and Groups').

Originally Posted by serpicojr

It sounds like the opposite of sphere packing--he's trying to get the worst packing, not the best.

I wouldn't bee too sure about that. The post title would suggest so, but not the problem statement.

The loosest circle packing in 2D is given by triplets of circles centered on the vertices of a hexagonal honeycomb. Packing fraction is 39%.

Well, it's been 3 years since I asked that question, but IIRC I was trying to figure out how to pick maximally different colors from a colorspace, maybe... maybe not. My memory's not too good. (Oh wait, yeah, I said as much in one of the posts.)

I'm not sure the hexagonal lattice satisfies my original question though, since you can add another circle of the same radius at the center of the hexagon. It's a loosest packing since none of the circles can move though. At least, I think that's how that works.

Originally Posted by MagiMaster

I'm not sure the hexagonal lattice satisfies my original question though, since you can add another circle of the same radius at the center of the hexagon. It's a loosest packing since none of the circles can move though. At least, I think that's how that works.

You can not add another circle of the same radius at the center of the hexagon, because in the set I described (it's not actually a packing. packings have circles in contact each other) the available space is just a tiny amount less than that required to allow you to do it.

Originally Posted by MagiMaster

First, a description of what I'm talking about: given a finite metric space, what is the minimum number of non-overlapping circles of a given radius that can cover the area so that no other circles can be added?

I suppose my main question is, is this a known, named problem? If so, what is it usually called?

Also, is this the same problem as asking how few overlapping circles can cover the whole space?

This will depend on the metric space. It is not obvious that the entire space can be covered by non-overlapping balls of any given fixed radius.

Well, the original question was in two parts.

First, with non-overlapping balls, how loose of a packing can you get if (instead of the usual 'none can move' criteria) you're looking for a point where no new balls can be added, even if the balls aren't touching.

Second, with overlapping circles, what's the loosest you can get that still covers the whole space.

Originally Posted by MagiMaster

Well, the original question was in two parts.

First, with non-overlapping balls, how loose of a packing can you get if (instead of the usual 'none can move' criteria) you're looking for a point where no new balls can be added, even if the balls aren't touching.

Second, with overlapping circles, what's the loosest you can get that still covers the whole space.

It still depends on the metric space. You have posed the question in too great a generality. With the right metric, squares can be circles and square packing can be perfectly tight.

The other thing is that a finite metric space is a discrete topological space, and hence not of much mathematical interest. I doubt that your problem has received any serious study.

What are you really trying to do ?

Well, I don't really remember anymore. I asked the original question a very long time ago. I think the space I had in mind was just [0,1]x[0,1]x[0,1] or the RGB colorspace and I was trying to pick out maximally distinct colors.

Originally Posted by MagiMaster

I was trying to pick out maximally distinct colors.

I've wondered about this too, did you ever find a good solution?

Not that I remember.