flaviu2001's blog

By flaviu2001, history, 4 years ago, In English

This is a problem that has baffled me for years. I kept thinking and the cases where n<=4 are simple enough but I can't figure a general pattern. So to explain the title a little take n=4 and arrange the n points in a square shape. So perhaps the points are (0,0) (1,0) (0,1) and (1,1). The largest segment is (1,1) — (0,0) and is length sqrt(2). The smallest segment is (0,0) — (1,0) and is length 1. So the ratio is sqrt(2)/1 = sqrt(2) and I am pretty sure this is the smallest ratio you can get for n=4. For n=3 you can arrange the points into an equilateral triangle for a ratio of 1, all the segments are the same length and for n=2 the ratio is also 1. I'm sure it's not as simple as placing the numbers into a regular polygon shape every time as placing one of the points inside the polygon will make more room between points keeping the longest distance relatively constant.

So if anyone has any sort of insight or even a solution for n=5 or n=6 I'd be very thankful!

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Looks similar to circle packing. You can get some ideas from there.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You're right, I also think now circle packing is the answer to the problem. Thanks for the link aswell, I'll look further into the theory on this.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Found the same question on math.SE. Answer seems to give an equivalence proof.

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I am not gonna give you exact answer, but some insight as to how optimum arrangement more or less looks like. You can just assume that smallest distance is 1 and what you are trying to do is to consider a set of points so that each pair is at distance at least 1 that has the smallest possible diameter. Or you can think of placing disjoint disks of radius 0.5. From that interpretation it looks intuitive to place them on a triangular grid within some disk of the smallest possible radius. From that you can determine that asymptotically the answer is $$$3^{\frac14} \pi^{-\frac12} \sqrt{n}$$$ if I am not mistaken, but to get a precise general formula for all values of $$$n$$$ — that could be very challenging if not impossible

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think I get the intuition, the points are regarded as non-overlapping circles of radius 0.5 to ensure the smallest distance is at least 1, but your goal is packing these circles in such a way that the distance between the circles is as small as possible, very akin to circle packing as mentioned above, because the circle is the object is smallest "diameter" given an area. I get now why the answer is O(sqrt(n)) because the area is O(n^2), all that is left is to ponder where the constants come from. Thanks man, you really scratched that big itch on my brain, I'm happy even with an approximation.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You should probably ask this in Math Stackexchange, or given how difficult this problem this looks like, Math Overflow. I refuse to believe this isn't a known problem, but I can't find any google results that are relevant. At risk of reinventing the wheel, here it goes:

Here, we assume any two points have a distance of at least 1. The problem becomes finding two points which have a distance of d, e.g. for n=4 we will show we must be able to find d >= sqrt(2)

n=4
n=5

I suspect a similar technique will work for as long as the optimal cases do not involve more than one point in centre, so probably upto 9 or 10.

Asymptotic case

I think it is very difficult to get exact answers for these types of problems.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Right?? The problem looks like something some obscure mathematician might have solved somewhere given its statement's simplicity. Yes I get what you are saying, I've convinced myself. Actually this is a construction I had thought of a long time ago, something like arranging points into regular polygons inside more regular polygons, and this is actually circle packing come to think of it. I just hadn't had the intuition of circles. Well I'm sure a closed formula is likely impossible and one might just have to do with the approximation of the answer but it is nice food for thought.