Minimax space-filling design for 2 dimensions in practice I think I understand the basic idea of a 2d minimax design. Given $n$ data points, choose locations for each point so that the maximum distance between anywhere in the input space and any of the $n$ points is minimized.
How do you do (or approximate) something like this in practice? E.g. for $[0,1]^2$ and $n=20$ what would be the algorithm?
 A: It's very closely related to the unit disk cover problem, but the unit disk being covered replaced by the unit square.
There are solutions for $n=1,2,\ldots,12$, depicted here. The values of $s$ there will be the inverse of the diameter of the smallest circles that cover the unit square.
Nurmela and Ostergard, (2000)$^{\text{[1]}}$  give an algorithm and show some solutions up to $n=30$.
Tarnai and Gáspár (1995)$^{\text{[2]}}$ give a lower bound on the minimum circle size for a given $n$.
-
There's a related problem here. I believe efficient solutions to this problem could be used to generate possible solutions for your problem, since you could use a root-finding algorithm (perhaps binary section) to find the circle size that causes the solution to jump up to the next largest value for the number of circles.
Many more papers can be located from this information and some reasonable facility with a search engine. (If you can't find any, let me know)
-
Some other possible approximations:

*

*a sometimes quite reasonable upper bound approximation for $n=k^2.m$ (e.g. n=4,8,9,12,16,18,20,24,25,27,28,32,36,... so quite a few values of $n$) can be obtained by tiling $k^2$ copies of the $m$-cover.


*If you have a solution for $n=m-1$, the solution for $n=m$ must be at least that small, since you can simply use the solution for $m-1$ and throw the extra circle on ... essentially anywhere. You might be able to explore some form of improvement from such a solution (perhaps via simulated annealing or some-such).
For large $n$, I'd probably always start with a hexagonal arrangement, though that $km^2$ trick could come in handy sometimes.
-
[1]: Kari J. Nurmela, and Patric R. J. Östergård, (2000),
Covering A Square With Up To 30 Equal Circles
citeseer
pdf
[2]: T. Tarnai, and Zs. Gáspár, (1995),
Covering a square by equal circles
Elem. Math., 50 (1995), pp. 167–170
paper (pdf available from that location)
