Keywords: design of experiments, space-filling, minimax, Voronoi diagram, largest empty sphere problem, optimization, evolutionary algorithms, evolution strategy.

Space-filling design strategies known as design of (computer) experiments (DoE) create an essential part of a surrogate model. Two main objectives are usually placed on the resulting designs - orthogonality and space-filling properties. The last decade has witnessed the development of several methods for the latter objective. One of the metrics, called minimax represents a very interesting research area. The authors think that this metric seems as the most suitable one for practical purposes, however its computation for higher dimensions is intractable and hence our paper presents new results on this subject.

Given a set of n points in a d-dimensional hypercube, the minimax is the radius of the biggest sphere with its center inside the hypercube that does not contain any point of the set. This problem is also known as an empty sphere problem [1]. In other words, the minimax serves as an estimation of the space-filling properties of the set of points showing the biggest unsampled space. One possible solution is to inspect all vertices forming a Voronoi diagram [2] of the given points. However, for the unbounded case the number of vertices grows exponentially and for the bounded case, i.e. the case of points inside a hypercube, the number is even higher. Although the boundary of the domain can be efficiently solved by mirroring [3], to reliably find the vertices of the Voronoi diagram in higher dimensions new algorithms are still needed.

Our paper follows the earlier work [4], where an evolutionary strategy has been used to find the center of the biggest empty sphere. We show that this approach is able to find exact solutions only up to five dimensions and no more. Therefore, an improved algorithm is proposed, where the evolution strategy is run in parallel on subdivisions of the original hypercube. The results show that our procedure is more robust that the referenced one. However an extension to high dimensional spaces, e.g. hundreds, is still not satisfactorily solved and therefore future improvements are needed.

1

M.T. Dickerson and D. Eppstein, "Algorithms for proximity problems in higher dimensions", Computational Geometry, 5(5):277-291, 1996.

2

A. Okabe, B. Boots, K. Sugihara, S.N. Chiu, "Spatial tessellations: Concepts and applications of Voronoi diagrams", Probability and Statistics. Wiley, NYC, 2nd edition, 2000. 671 pages.

3

L. Pronzato and Werner G. Müller, "Design of computer experiments: space filling and beyond", Statistics and Computing, 22(3):681-701, 2012.

4

J.S. Lee, T.S. Cho, J. Lee, M.K. Jang, T.K. Jang, D. Nam, C.H. Park, "A stochastic search approach for the multidimensional largest empty sphere problem", Citeseer, URL, 2004.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £40 +P&P)