Notices
Results 1 to 21 of 21

Thread: Loosest circle packing

  1. #1 Loosest circle packing 
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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?


    Reply With Quote  
     

  2.  
     

  3. #2 Re: Loosest circle packing 
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Sounds like the sphere-packing problem to me.


    Reply With Quote  
     

  4. #3  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    It sounds like the opposite of sphere packing--he's trying to get the worst packing, not the best.
    Reply With Quote  
     

  5. #4  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  6. #5  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    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.
    Reply With Quote  
     

  7. #6  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  8. #7  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    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?
    Reply With Quote  
     

  9. #8  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  10. #9  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    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<sub>1</sub>), ..., B(r/2,x<sub>k</sub>). So, for any y in X, there must exist some i such that B(r/2,x<sub>i</sub>) and B(r/2,y) have nontrivial intersection, say the point z lies in their intersection. But then d(x<sub>i</sub>,y) ≤ d(x<sub>i</sub>,z) + d(z,y) < r. So you can cover X by the balls B(r,x<sub>i</sub>), and X is totally bounded.

    So we should restrict our attention to totally bounded spaces.
    Reply With Quote  
     

  11. #10  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    Isn’t that the same as saying that the space is compact?
    Reply With Quote  
     

  12. #11  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    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|<sub>p</sub> = 0.
    -If n = p<sup>k</sup>r, (p,r) = 1, k ≥ 0, then |n|<sub>p</sub> = p<sup>-k</sup>

    Now define the p-adic metric:

    d(x,y) = |x-y|<sub>p</sub>

    [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<sup>k</sup>Z, and so clearly this space is totally bounded.

    Now define a system of open sets as follows:

    -Let U<sub>1</sub> = pZ.
    -Let U<sub>2</sub> = 1+p<sup>2</sup>Z.
    -In general, let U<sub>n</sub> = x<sub>n</sub>+p<sup>n</sup>Z, where |x<sub>n</sub>| (usual absolute value here) is minimal among integers not in any of the U<sub>k</sub> 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!
    Reply With Quote  
     

  13. #12 Re: Loosest circle packing 
    New Member
    Join Date
    Mar 2011
    Posts
    3
    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').
    Reply With Quote  
     

  14. #13  
    New Member
    Join Date
    Mar 2011
    Posts
    3
    Quote 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%.
    Reply With Quote  
     

  15. #14  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  16. #15  
    New Member
    Join Date
    Mar 2011
    Posts
    3
    Quote 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.
    Reply With Quote  
     

  17. #16 Re: Loosest circle packing 
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote 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.
    Reply With Quote  
     

  18. #17  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  19. #18  
    . DrRocket's Avatar
    Join Date
    Aug 2008
    Posts
    5,486
    Quote 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 ?
    Reply With Quote  
     

  20. #19  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    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.
    Reply With Quote  
     

  21. #20  
    Forum Freshman
    Join Date
    Aug 2010
    Posts
    97
    Quote 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?
    Reply With Quote  
     

  22. #21  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Not that I remember.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •