Equidistant points across a cube

Question

I need to initialize some three dimensional points, and I want them to be equally spaced throughout a cube. Are there any creative ways to do this?

I am using an iterative Expectation Maximization algorithm and I want my initial vectors to "span" the space evenly.

For example, suppose I have eight points that I want to space equally in a cube sized 1x1x1. I would want the points at the corners of a cube with a side length of 0.333, centered within the larger cube.

A 2D example is below. Notice that the red points are equidistant from eachother and the edges. I want the same for 3D.

In cases where the number of points does not have an integer cube root, I am fine with leaving some "gaps" in the arrangement.

Currently I am taking the cube root of the number of points and using that to calculate the number of points and the desired distance between them. Then I iterate through the points and increment the X, Y and Z coordinates (staggered so that Y doesn't increment until X loops back to 0, same for Z with regard for Y).

If there's an easy way to do this in MATLAB, I'd gladly use it.

Answer 1

The sampling strategy you are proposing is known as a Sukharev grid, which is the optimal low dispersion sampling strategy, http://planning.cs.uiuc.edu/node204.html. In cases where the number of samples is not n^3, the selection of which points to omit from the grid is unimportant from a sampling standpoint.

In practice, it's possible to use low discrepancy (quasi-random) sampling techniques to achieve very good results in three dimensions, http://planning.cs.uiuc.edu/node210.html. You might want to look at using Halton and Hammersley sequences.

• http://en.wikipedia.org/wiki/Halton_sequence
• http://en.wikipedia.org/wiki/Constructions_of_low-discrepancy_sequences