How to generate a set of K points evenly spaced in unit cube/sphere of dimension D

Question

I'm trying to generate a set of K points that are evenly spread out inside a fixed space, I figured a unit sphere or cube would be easiest. It was easy enough for 2 dimensions, but it is a lot harder as we go up to arbitrary dimension D, unfortunately.

I think this is done in "quasi Monte Carlo methods" but I've been unable to find a formula, or even a statement as to whether this is a tractable problem. Any input would be appreciated.

Answer 1

It depends what you mean by "evenly." One approach is to position the points randomly and then simulate particle movement in a damping medium with an numerical integrator of Newton's motion equations, where particles and the boundary are mutually repulsive. This will of course allow any boundary shape at all.

Answer 2

To see that calculating the best case is "not trivial" look at the paper Dense Packings of Equal Spheres in a Cube which addresses the subcase of points in a 3D cube: It has exact solutions and "best-known" solutions for only upto 28 points.

It does present an algorithm for finding these optimally spaced configurations, which they call the "Stochastic Billiard" procedure. However I do not know whether this can be adapted to spheres, higher dimensions or larger numbers of points.

It also looks like some aspects of the more general case may be covered in the book Finite Packing and Covering - (which I dont have a copy of, so can't verify.)

The 2D case is much more tractable, and you can see further details on wikipedia for the square and the circle.

Answer 3

Let's consider the cube as it's easier (I originally said easy, haha). I assume this is what you want (in 3D):

The number of points on a side is n = floor(K^1/D). Then the spacing between points is 1 / (n - 1), assuming corners and edges are inclusive. I was going to offer some code for this grid approach, but it's quite ugly and the solution isn't ideal.

Answer 4

I am not sure I completely understood your question but here is my go at it.

public static List<int[]> getEvenSpacedPoints(int x0, int x1, int y0,
        int y1, int z0, int z1, int samplePerSide) {

    List<int[]> list = new ArrayList<>();
    int xSpacing = (x1 - x0) / samplePerSide;
    int ySpacing = (y1 - y0) / samplePerSide;
    int zSpacing = (z1 - z0) / samplePerSide;

    for (int i = 0; i < samplePerSide; i++) {
        for (int j = 0; j < samplePerSide; j++) {
            for (int w = 0; w < samplePerSide; w++) {
                int xPoint = xSpacing * i;
                int yPoint = ySpacing * j;
                int zPoint = zSpacing * w;
                int[] point = new int[] { xPoint, yPoint, zPoint };
                list.add(point);
            }
        }

    }
    return list;
}

And

List<int[]> setOfSamplesFromCube = getEvenSpacedPoints(0, 10, 0, 10, 0,
            10, 5);
    for (int[] point : setOfSamplesFromCube) {
        String ret = "";
        for (int value : point) {
            ret += value + ",";
        }
        System.out.println(ret);
    }

Out:

0,0,0,
0,0,2,
0,0,4,
0,0,6,
0,0,8,
0,2,0,
0,2,2,
0,2,4,
0,2,6,
0,2,8,
0,4,0,
0,4,2,
0,4,4,
0,4,6,
0,4,8,
0,6,0,
0,6,2,
0,6,4,
0,6,6,
0,6,8,
0,8,0,
0,8,2,
0,8,4,
0,8,6,
0,8,8,
2,0,0,
2,0,2,
2,0,4,
2,0,6,
2,0,8,
2,2,0,
2,2,2,
2,2,4,
2,2,6,
2,2,8,
2,4,0,
2,4,2,
2,4,4,
2,4,6,
2,4,8,
2,6,0,
2,6,2,
2,6,4,
2,6,6,
2,6,8,
2,8,0,
2,8,2,
2,8,4,
2,8,6,
2,8,8,
4,0,0,
4,0,2,
4,0,4,
4,0,6,
4,0,8,
4,2,0,
4,2,2,
4,2,4,
4,2,6,
4,2,8,
4,4,0,
4,4,2,
4,4,4,
4,4,6,
4,4,8,
4,6,0,
4,6,2,
4,6,4,
4,6,6,
4,6,8,
4,8,0,
4,8,2,
4,8,4,
4,8,6,
4,8,8,
6,0,0,
6,0,2,
6,0,4,
6,0,6,
6,0,8,
6,2,0,
6,2,2,
6,2,4,
6,2,6,
6,2,8,
6,4,0,
6,4,2,
6,4,4,
6,4,6,
6,4,8,
6,6,0,
6,6,2,
6,6,4,
6,6,6,
6,6,8,
6,8,0,
6,8,2,
6,8,4,
6,8,6,
6,8,8,
8,0,0,
8,0,2,
8,0,4,
8,0,6,
8,0,8,
8,2,0,
8,2,2,
8,2,4,
8,2,6,
8,2,8,
8,4,0,
8,4,2,
8,4,4,
8,4,6,
8,4,8,
8,6,0,
8,6,2,
8,6,4,
8,6,6,
8,6,8,
8,8,0,
8,8,2,
8,8,4,
8,8,6,
8,8,8,

This includes the starting point (start loop on 1 if want to omit) and is "easy" because the cube I passed to it has nice sides that is divisible by 5, otherwise integer division would ruin this, but you can see how it can easily be changed to return a double-list.

I will start trying for a D dimensional case..