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

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

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?

And the number of dimensions, which I intentionally did not mention... I do know this: for four points, x/y can be equal to 1 Reveal Hidden Content. For five, my powers of visualisation fail me, but Reveal Hidden Content. Proof of this is left as an exercise for the reader.

Richard

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.

I agree with this reasoning for some sufficiently large number of points in the plane. However, I am not sure how this translates to, say, the initial problem of 6 points in the plane. I do not really know the answer yet. The best I have come up with is the same as what Palynka proposed, but I do not have a proof that it is the minimum. I do have a proof that, for example, the answer cannot be less than y/x = sqrt(3). But that does not help that much.

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.

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.

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.

Sorry, instead of "any" I should have written "every", tricky language, English 🙂

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?

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 have to run an undetermined number of starting conditions, rather at random, across the range of possibilities, and will still have a potential failure to find the global optimum. I don't know why I'm telling YOU this, maybe just that you triggered this memory.

http://www.chem.uoa.gr/applets/AppletSimplex/Appl_Simplex2.html

example f6 at this demo can show this effect.

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.

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.

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.

Hmm, I have tried (and so far failed) to set rules fora given set of random points which will "attract" it towards an optimum solution, so I looked at the simplex idea. However that hits the problem below:

To start off, we generate N+1 sets of points, where N is the number of points in each set. In step one we order them all by "goodness", which is here how low their largest/smallest is. So far so good.

But in step 2 we need to calculate the average, what is the average of a set of sets of points? I am stumped by this. Say I have 4 points in a line, 4 points at the corners of a square, and 4 points making an equilateral triangle with a centre points; how do I generate a new set of 4 points that is the "average" of all of those?


Can anyone help? Does anyone have any ideas? If the shapes were similar I could put them all at the same orientation and take the average of each point, but this does not work with dissimilar shapes....

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.

Cool posting Taz :-)
Considering it, I have just realised that the polygon problem is equivalent to the following problem regarding clrcles:

If 6 circles of equal radius are placed such that they all overlap and each circle's centre is within (or on the edge of) the joint overlap, then what is the layout that makes the distance between the closest two circle centres as large as possible.

I wonder if the problem is easier to solve in that form?

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.