In a restricted space with n dimension, how to find the coordinates of p points, so that they are as far as possible from each other?

Question

For example, in a 2D space, with x [0 ; 1] and y [0 ; 1]. For p = 4, intuitively, I will place each point at each corner of the square.

But what can be the general algorithm?

Answer 1

Edit: The algorithm needs modification if dimensions are not orthogonal to eachother

To uniformly place the points as described in your example you could do something like this:

var combinedSize = 0

for each dimension d in d0..dn {
    combinedSize  += d.length;
}

val listOfDistancesBetweenPointsAlongEachDimension = new List

for each d dimension d0..dn {
    val percentageOfWholeDimensionSize = d.length/combinedSize
    val pointsToPlaceAlongThisDimension = percentageOfWholeDimensionSize * numberOfPoints
    listOfDistancesBetweenPointsAlongEachDimension[d.index] = d.length/(pointsToPlaceAlongThisDimension - 1)
}   

Run on your example it gives:

combinedSize = 2

percentageOfWholeDimensionSize = 1 / 2

pointsToPlaceAlongThisDimension = 0.5 * 4

listOfDistancesBetweenPointsAlongEachDimension[0] = 1 / (2 - 1) listOfDistancesBetweenPointsAlongEachDimension[1] = 1 / (2 - 1)

note: The minus 1 deals with the inclusive interval, allowing points at both endpoints of the dimension

Answer 2

1. 2D case

   In 2D (n=2) the solution is to place your p points evenly on some circle. If you want also to define the distance d between points then the circle should have radius around:

   2*Pi*r = ~p*d
   r = ~(p*d)/(2*Pi)
   

   To be more precise you should use circumference of regular p-point polygon instead of circle circumference (I am too lazy to do that). Or you can compute the distance of produced points and scale up/down as needed instead.

   So each point p(i) can be defined as:

   p(i).x = r*cos((i*2.0*Pi)/p)
   p(i).y = r*sin((i*2.0*Pi)/p)
   

2. 3D case

   Just use sphere instead of circle.

3. ND case

   Use ND hypersphere instead of circle.

So your question boils down to place p "equidistant" points to a n-D hypersphere (either surface or volume). As you can see 2D case is simple, but in 3D this starts to be a problem. See:

• Make a sphere with equidistant vertices
• sphere subdivision triangulation

As you can see there are quite a few approaches to do this (there are much more of them even using Fibonacci sequence generated spiral) which are more or less hard to grasp or implement.

However If you want to generalize this into ND space you need to chose general approach. I would try to do something like this:

1. Place p uniformly distributed place inside bounding hypersphere

   each point should have position,velocity and acceleration vectors. You can also place the points randomly (just ensure none are at the same position)...

2. For each p compute acceleration

   each p should retract any other point (opposite of gravity).

3. update position

   just do a Newton D'Alembert physics simulation in ND. Do not forget to include some dampening of speed so the simulation will stop in time. Bound the position and speed to the sphere so points will not cross it's border nor they would reflect the speed inwards.

4. loop #2 until max speed of any p crosses some threshold

This will more or less accurately place p points on the circumference of ND hypersphere. So you got minimal distance d between them. If you got some special dependency between n and p then there might be better configurations then this but for arbitrary numbers I think this approach should be safe enough.

Now by modifying #2 rules you can achieve 2 different outcomes. One filling hypersphere surface (by placing massive negative mass into center of surface) and second filling its volume. For these two options also the radius will be different. For one you need to use surface and for the other volume...

Here example of similar simulation used to solve a geometry problem:

• How to implement a constraint solver for 2-D geometry?

Here preview of 3D surface case:

The number on top is the max abs speed of particles used to determine the simulations stopped and the white-ish lines are speed vectors. You need to carefully select the acceleration and dampening coefficients so the simulation is fast ...