I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly constant throughout the grid (avoid points concentrating in certain regions as much as possible).
This problem seems to be quite tough (I am not a mathematician so I did not know that beforehand :). I found this paper that seemed to address a similar problem, and there they mention that a good strategy if you have a grid that is $2^k \times 2^k$ (which I can make because my grid is arbitrary) is to pick the largest empty circle and place the point at its center. So my questions are:
- Is that so?
- If it is, how do I guarantee that if I get several largest circles I don't accumulate the points as I am placing the points online?
- What is a good way to implement that? I am looking at matlab but it does not seem obvious to me how to compute the largest available circle every time (I would have to sweep all the available points for placement and compute this, which will take long time). But again I am not a computer science guy either.
Any hint / help would be appreciated.
Thanks!
EDIT: to be more specific based on the comments so far, I should say that I have tried a couple of things: 1) a code I found in http://www.softimageblog.com/archives/115 posted by Anton Sherwood, which uses two relatively prime numbers to generate a pattern. This can create adequate patterns for certain combinations in R^2 but when I round the result it groups the points. I though this approach was the Halton sequences because of the prime numbers but I am not sure now. 2) I used a true Halton sequence following one of the comments, but this gave a somewhat random distribution (which is what it is supposed to do)
My problem is deterministic, as I know my grid (actually I can chose it arbitrarily with some constraints) and I also know the number of points I want to place inside, so I was more looking for a deterministic approach to place the points to achieve even distribution (as in the paper I first mentioned).
Again thanks for the help and sorry for the confusion.
Check out the Halton sequence and some other low-discrepancy sequences.