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!
Looks similar to circle packing. You can get some ideas from there.
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.
Found the same question on math.SE. Answer seems to give an equivalence proof.
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
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.
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; Square is optimal. We can show this by considering convex hull.
4 points convex hull: Then since interior angle sums to 360, at least one must be 90 degrees. Using cosine law on 1,1,90 degrees, at least one side must have length sqrt(2).
3 Points convex hull: Suppose P is in the interior of ABC, then at least one of APB,BPC,CPA is of 120 degrees , as they sum to 360. Then using cosine law, you get 1,1,120 degrees into sqrt(3). This is > sqrt(2).
n=5: Pentagon is optimal. Go by convex hull classifications again.
5 points convex hull: An angle must be >= 108 degree, because they sum to 540. This will give d at least what we found for the regular pentagon.
4 Point convex hull: Let A,B,C,D be in this order ( say clockwise), P in interior. We just have to show one of APB,BPC,CPD,DPA,APC,BPD is >= 108 degrees. Suppose not, say direction of A from P is 0 degrees, then possible direction for B is [0,108] and possible direction for C is in [0,216] note that 360-216 = 144 > 108, so APC <= 108 actually means C can only be in range [0,108] . Similarly , we find [0,108] for D . so All of A,B,C,D lie on the same side of P , and cannot be a convex hull.
3: the 4 case show we must get a root(3). Actually, root(3) > (1+ sqrt(5))/2 which is the number for pentagon. So we are done.
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.
It is actually fairly easy to show the answer is O(sqrt(n)).
Proof is by area counting. Consider a radius 1/2 circle from each point. By condition, they do not intersect. However, if the maximum distance is d , all these fit inside an circle of diameter (2d+1) (Yes, this is gross overestimation). Therefore , if there are n points, we have O((d)^2) < n.
You can construct an O(sqrt(N)) example by regular triangle tiling.
I think it is very difficult to get exact answers for these types of problems.
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.