A stochastic search approach for the multidimensional largest empty sphere problem
Jong‐Seok Lee, Taeg-Sang Cho, Jiye Lee, Myung-Kee Jang, Taekwang Jang, Dongkyung Nam, Cheol Hoon Park · 2004
This paper presents a novel approach to solve the largest empty sphere (LES) problem in the multidimensional space by using a popular stochastic search approach, evolutionary algorithm (EA). When a set of points are given in a space, the LES problem is to nd a point from which the distance to the nearest point among the set is maximized. Conventionally, the LES problem can be solved by the use of the Voronoi diagram which is a useful data structure in the eld of computational geometry. However, we have difculty in constructing the Voronoi diagram in the high-dimensional space because the time and the storage complexities grow exponentially as the dimension of the problem becomes high. In this paper, an EA approach is used as an effective method of nding the solution of the LES problem in the multidimensional Euclidean space. Experimental results show that the proposed method successfully nds the solutions of the LES problems in various dimensional spaces and is efcient in terms of the execution time and the necessary memory in comparison with the Voronoi diagram approach.