<p>The optimal centroidal Voronoi tessellation for the infinite 2D grid is a <a href="https://orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf" rel="nofollow">hexagon tiling</a>.</p>

<p>You can get one of these by placing points at even coordinates on even rows and odd coordinates for odd rows. Depends on the number of points you need.</p>

<p>Start with that then run <a href="http://en.wikipedia.org/wiki/Lloyd%27s_algorithm" rel="nofollow">Lloyd's algorithm</a> for a few iterations to tidy up the corners and edges.</p>

<p>I would compute it offline on a unit square to good precision, then dilate it to your chosen rectangle with a simple linear transformation.</p>

CC BY-SA 3.0
2014-03-12T15:57:09.493Z
This looks good, but I'm afraid Lloyd's algorithm is too complex to be reasonably fast. (As opposed to dithering, which can be computed in a simple nested loop, O(N^2) runtime.) It's still a lot of help because somehow I couldn't this or any algorithm at all. But I don't understand the precomputation possibility: does it work if M varies wildly?
fejesjoco
CC BY-SA 3.0
2014-03-12T16:07:23.677Z
The quantization tolerance is much better for large $M$, it is the small $M$ where you have to be really precise and want a high accuracy lookup table. Lloyds is $O( log(M)*S*I)$ where $S$ is the number of random samples and $I$ is the number of iterations. If you are maxing it to $S = N^2$ then each iteration takes just as long as your dither.
Chad Brewbaker
CC BY-SA 3.0
2014-03-12T15:39:49.153Z
2014-03-12T15:39:49.153Z
Chad Brewbaker
<p>In an NxN grid, I want to select M points (<span class="math-container">$1 \leq M \leq N^2$</span>) so that they are distributed as evenly as possible, spread out everywhere, edge to edge. <strong>Can you suggest a fast algorithm for distributing points evenly over a grid?</strong></p>
<p>I won't yet try to formally define &quot;evenly&quot;, because it's not an exact requirement. Low runtime is the most important factor here, so algorithms like &quot;do a random distribution and refine until it satisfies a criteria&quot; are bad, I prefer doing it in a simple nested loop.</p>
<hr />
<h3>Examples</h3>
<p>Let me illustrate with some examples.</p>
<p>When M is a square number, the solution is simple, let's say N=5 and M=9:</p>
<pre><code>trivial
#.#.#
.....
#.#.#
.....
#.#.#
</code></pre>
<p>It can also work in some special cases when M can be written as a sum of squares, and there's no interference between the squares, for example N=5 and M=13=9+4:</p>
<pre><code>two square patterns
#.#.#
.X.X.
#.#.#
.X.X.
#.#.#
</code></pre>
<p>But this wouldn't exactly work for M=10, because after you select 9 points in a square pattern, there's no good place to put the 10th one.</p>
<p>My first shot at this was an image dithering algorithm. It looked pretty good when M was big enough, but with small M's, the error distribution makes it biased towards the edges. For example with N=3 and M=1, dithering yields a bad result when a good result is pretty obvious:</p>
<pre><code>bad  good
...  ...
...  .#.
..#  ...
</code></pre>
<p>Let me show another example of a bad and good distribution with N=5 and M=5:</p>
<pre><code>bad    good   bad    good
#....  #...#  .....  .#...
.#...  .....  .#.#.  ....#
..#..  ..#..  ..#..  ..#..
...#.  .....  .#.#.  #....
....#  #...#  .....  ...#.
</code></pre>
<p>I'll tell you an idea for a formal definition of &quot;evenly&quot;. But as I said, it doesn't have to be exactly like that, it's more of an intuitive thing. So how about this: let's take every 2x2, 3x3, ... N-1xN-1 subsquare and count the point density in each of them. The deviation of those numbers should be as small as possible. Let's see for N=4 and M=4:</p>
<pre><code>one   two
#.#.  #..#
....  ....
#.#.  ....
....  #..#
</code></pre>
<p>One:</p>
<ul>
<li>2x2 sums: 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4</li>
<li>3x3 sums: 4/9, 2/9, 2/9, 1/9</li>
<li>stddev: 0.06991</li>
</ul>
<p>Two:</p>
<ul>
<li>2x2 sums: 1/4, 0, 1/4, 0, 0, 0, 1/4, 0, 1/4</li>
<li>3x3 sums: 1/9, 1/9, 1/9, 1/9</li>
<li>stddev: 0.10758</li>
</ul>
<p>(Even though number two has a higher deviation, it is spread edge to edge, so I prefer it a little, but number one works as well. Dealing with the edges is a not-so important edge-case.)</p>

<ds.algorithms><application-of-theory>
Fast algorithm to distribute points evenly in a 2D grid
fejesjoco
# Fast algorithm to distribute points evenly in a 2D grid

(Asked by: username_0 on 2014-03-12)

In an NxN grid, I want to select M points ($1 \leq M \leq N^2$) so that they are distributed as evenly as possible, spread out everywhere, edge to edge. Can you suggest a fast algorithm for distributing points evenly over a grid?
I won't yet try to formally define "evenly", because it's not an exact requirement. Low runtime is the most important factor here, so algorithms like "do a random distribution and refine until it satisfies a criteria" are bad, I prefer doing it in a simple nested loop.

Examples
Let me illustrate with some examples.
When M is a square number, the solution is simple, let's say N=5 and M=9:
trivial
#.#.#
.....
#.#.#
.....
#.#.#

It can also work in some special cases when M can be written as a sum of squares, and there's no interference between the squares, for example N=5 and M=13=9+4:
two square patterns
#.#.#
.X.X.
#.#.#
.X.X.
#.#.#

But this wouldn't exactly work for M=10, because after you select 9 points in a square pattern, there's no good place to put the 10th one.
My first shot at this was an image dithering algorithm. It looked pretty good when M was big enough, but with small M's, the error distribution makes it biased towards the edges. For example with N=3 and M=1, dithering yields a bad result when a good result is pretty obvious:
bad  good
...  ...
...  .#.
..#  ...

Let me show another example of a bad and good distribution with N=5 and M=5:
bad    good   bad    good
#....  #...#  .....  .#...
.#...  .....  .#.#.  ....#
..#..  ..#..  ..#..  ..#..
...#.  .....  .#.#.  #....
....#  #...#  .....  ...#.

I'll tell you an idea for a formal definition of "evenly". But as I said, it doesn't have to be exactly like that, it's more of an intuitive thing. So how about this: let's take every 2x2, 3x3, ... N-1xN-1 subsquare and count the point density in each of them. The deviation of those numbers should be as small as possible. Let's see for N=4 and M=4:
one   two
#.#.  #..#
....  ....
#.#.  ....
....  #..#

One:

2x2 sums: 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4
3x3 sums: 4/9, 2/9, 2/9, 1/9
stddev: 0.06991

Two:

2x2 sums: 1/4, 0, 1/4, 0, 0, 0, 1/4, 0, 1/4
3x3 sums: 1/9, 1/9, 1/9, 1/9
stddev: 0.10758

(Even though number two has a higher deviation, it is spread edge to edge, so I prefer it a little, but number one works as well. Dealing with the edges is a not-so important edge-case.)

**Tags:** ds.algorithms, application-of-theory


---

## 1 answers

### Answer by username_1 on 2014-03-12. Score: 2 | Accepted answer

The optimal centroidal Voronoi tessellation for the infinite 2D grid is a [hexagon tiling](https://orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf).

You can get one of these by placing points at even coordinates on even rows and odd coordinates for odd rows. Depends on the number of points you need.

Start with that then run [Lloyd's algorithm](http://en.wikipedia.org/wiki/Lloyd%27s_algorithm) for a few iterations to tidy up the corners and edges.

I would compute it offline on a unit square to good precision, then dilate it to your chosen rectangle with a simple linear transformation.

> **Comments:**
> **username_0**: This looks good, but I'm afraid Lloyd's algorithm is too complex to be reasonably fast. (As opposed to dithering, which can be computed in a simple nested loop, O(N^2) runtime.) It's still a lot of help because somehow I couldn't this or any algorithm at all. But I don't understand the precomputation possibility: does it work if M varies wildly?  
> **username_1**: The quantization tolerance is much better for large $M$, it is the small $M$ where you have to be really precise and want a high accuracy lookup table. Lloyds is $O( log(M)*S*I)$ where $S$ is the number of random samples and $I$ is the number of iterations. If you are maxing it to $S = N^2$ then each iteration takes just as long as your dither.  

---

