Maximin Designs

The problem of finding the maximal common radius of n circles which can be packed into a square is equivalent to the maximin design problem. Melissen (1997) gives a comprehensive overview of the historical developments and state-of-the-art research in this field. For the L2-distance measure optimal solutions are known for n<21, and many good approximating solutions have been found for n>20; see Specht's Packomania website. Baer (1992) solved the maximum Linf-ball packing problem in a d-dimensional unit cube. The L1-circle packing problem in a square has been solved for many values of n; see Fejes Toth (1971) and Florian (1989).

All the results mentioned above are for non-LHD designs. Van Dam et al. (2007) derive maximin LHDs in two dimensions for the L1 and Linf-distance measure. Using a branch-and-bound technique they were able to find two-dimensional maximin LHDs for the L2-distance measure for n<71. For n>70 they found periodic and adapted periodic LHDs as approximations for the L2-maximin LHDs.

As finding maximin LHDs can be time-consuming for higher dimensions and larger values of n, most results in this field concern heuristical maximin LHDs, heuristical meaning that it is not guaranteed that the separation distance is maximal. In Van Dam et al. (2009), heuristical two-dimensional L2-maximin LHDs are constructed for up to 1000 points by optimizing a periodic structure. In Husslage et al. (2011), this is extended to more dimensions. Furthermore, heuristical L2-maximin LHDs for up to ten dimensions and for up to 300 design points are obtained using the enhanced stochastic evolutionary algorithm of Jin et al. (2005). Morris and Mitchell (1995) use a simulated annealing approach to obtain heuristical L1- and L2-maximin LHDs for up to five dimensions and up to 12 points and a few larger values.

All these designs have been compared and the best designs are collected on this website. They can be downloaded for free and used in your specific simulation environment.

Baer, D. (1992). Punktverteilungen in Würfeln beliebiger Dimension bezüglich der Maximum-norm, Wiss. Z. Pädagoh. Hochsch. Erfurt/Mühlhausen, Math.-Naturwiss. Reihe 28, 87-92.
Dam, E.R. van, B.G.M. Husslage, D. den Hertog, and J.B.M. Melissen (2007). Maximin Latin hypercube designs in two dimensions, Operations Research 55 (1), 158-169.
Dam, E.R. van, G. Rennen, B.G.M. Husslage (2009). Bounds for maximin Latin hypercube designs, Operations Research 57(3), 595-608
Florian, A. (1989). Verteilung von Punkten in einem Quadrat, Sitzungsber., Abt. II, Österr. Akad. Wiss., Math.-Naturwiss. Kl. 198, 27-44.
Husslage, B.G.M., G. Rennen, E.R. van Dam, and D. den Hertog (2011). Space-filling Latin hypercube designs for computer experiments, Optimization and Engineering 12, 611-630.
Jin, R., W. Chen, and A. Sudjianto (2005). An efficient algorithm for constructing optimal design of computer experiments, Journal of Statistical Planning and Inference, 134(1), 268-287.
Melissen, J.B.M. (1997). Packing and convering with circles, Ph.D. Thesis, ISBN 90-393-1500-0, Utrecht.
Morris, M.D., and T.J. Mitchell (1995) Exploratory designs for computational experiments, Journal of Statistical Planning and Inference 43, 381-402.