Six Points

Originally posted by Shallow Blue
Here's a nice variation:

Suppose you have five different points. Suppose that the smallest distance between any two of the five points is x. Suppose that the largest distance between any two of the five points is y. Under this scenario, what is the minimum possible value of y/x?

Richard

Here is a proof that regular polygons, with or without a centre point, are not the optimum answer to this problem for any number of points.

Consider a large number of points, in a regular polygon they will form an almost perfect circle, which will have a very small smallest distance (between two adjacent points on the edge) and a large distance equal to the radius, or double that if there is no centre point.

Take one of those points out of the edge of the circle and put it somewhere in the middle, it is easy to see that it can be put into the middle without changing the largest distance, and if we respace the perimiter points so they are again at equal spacing round the edge, the smallest distance will increase: We can clearly put a lot of points into the middle before the distance between the points in the middle approaches anything like the distance between the points at the edge.

Therefore, at a large enough number of points, the solution with one or zero points in the middle of a regular polygon is clearly not optimum.

Originally posted by JS357
I wonder if you don't need to specify the geometry: solid, hyperbolic, elliptic, some other non-Eulidean geometry?

Reveal Hidden Content

Reveal Hidden Content

Originally posted by iamatiger
Here is a proof that regular polygons, with or without a centre point, are not the optimum answer to this problem for any number of points.

Consider a large number of points, in a regular polygon they will form an almost perfect circle, which will have a very small smallest distance (between two adjacent points on the edge) and a large distance equal to ...[text shortened]... the solution with one or zero points in the middle of a regular polygon is clearly not optimum.

Originally posted by iamatiger
Here is a proof that regular polygons, with or without a centre point, are not the optimum answer to this problem for any number of points.

Consider a large number of points, in a regular polygon they will form an almost perfect circle, which will have a very small smallest distance (between two adjacent points on the edge) and a large distance equal to ...[text shortened]... the solution with one or zero points in the middle of a regular polygon is clearly not optimum.

Originally posted by Palynka
But that's not true for the 3 point case and we haven't found a closer answer than a pentagon for the 5 (and 6 with the centroid) point case... In the beginning you say for any number of points, but at the end you correct for large enough N (with which I agree with you). As for my terrible proposed rule, yep, it's completely wrong, you've already proven it before.

I'm wondering if I can:
a) Select N random point positions:
b) Join them all with little springs, such that the closest 2 are being pushed apart, the furthest 2 are being pulled together, and other distances are interpolated.
c)Inject a little random "heat"into the points, simulate a small random friction, and see where the points end up.

What do you all think, might this give us some insights?

Originally posted by iamatiger
I'm wondering if I can:
a) Select N random point positions:
b) Join them all with little springs, such that the closest 2 are being pushed apart, the furthest 2 are being pulled together, and other distances are interpolated.
c)Inject a little random "heat"into the points, simulate a small random friction, and see where the points end up.

What do you all think, might this give us some insights?

Originally posted by JS357
A long time ago I studied and applied a simplified form of simplex optimization, in analytical chemistry method development. The problem with such optimization methods is that they can find the nearest local optimum, but if it is surrounded in all directions by a less optimal solution, it will never move from there to a more optimal global solution. So you hav ...[text shortened]... a.gr/applets/AppletSimplex/Appl_Simplex2.html

example f6 at this demo can show this effect.

Originally posted by iamatiger
Yeah, I didn't think it would find *the* optimum, just that with a little heat (random jiggles to point velocities), and a few particles, and several runs, it probably would give a good guess. Then i could try it on 3 points upwards and see which shapes it got.

Perhaps like this.. a variant of the drift idea.

Pick two points to start with. Those are the ones that are the farthest apart and their locations are fixed. Say, (1,0) and (0,0). Then place the other four randomly in the area between them so that all 15 mutual distances are 1 or less. Find the pair that is closest to each other, and bump them away from each other, very little, without violating the maximum distance condition and without approaching any other point. Repeat a couple of thousand times to find a stable solution, save it, and start over for another stable solution.

That's a brute force, gordion solution to the problem.. not elegant at all.. but it does work.

Originally posted by talzamir
Perhaps like this.. a variant of the drift idea.

Pick two points to start with. Those are the ones that are the farthest apart and their locations are fixed. Say, (1,0) and (0,0). Then place the other four randomly in the area between them so that all 15 mutual distances are 1 or less. Find the pair that is closest to each other, and bump them away from ...[text shortened]...
That's a brute force, gordion solution to the problem.. not elegant at all.. but it does work.

Ah! It gets *even* easier if we keep the smallest length constant:

Imagine the optimal arrangement, with smallest length S. At least 2 points must be S apart, and no points closer together than S. So we can draw circles of radius S/2 around each point and no circles will overlap, with at least 2 touching.

So, instead of finding the best arrangement of N points, we can can find the arrangement of N circles, such that no circles overlap and the furthest distance between any two circles is as small as possible. The centre of those circles are the points in the best solution.

It is then very easy to see that a hexagonally close packed tiling of the plane is the limit as N approaches infinity.

For lower N, does anyone else think we can find the optimum by finding the smallest circle within which N smaller circles can be packed? If so, see: http://en.wikipedia.org/wiki/Circle_packing_in_a_circle

Put that way, I'm fairly convinced. Though the closest tiling sounds more like fitting into a smallest area than minimizing the highest distance. There can be some oddities along the way, but generally it will probably be a beehive.