Iterative method for constructing coverings of the multidimensional unit sphere. (Russian, English) Zbl 1274.49059

Zh. Vychisl. Mat. Mat. Fiz. 53, No. 2, 181-194 (2013); translation in Comput. Math. Math. Phys. 53, No. 2, 131-143 (2013).
Summary: The Stepwise-Supplement-of-a-Covering (SSC) method is described and examined. The method is intended for the numerical construction of near optimal coverings of the multidimensional unit sphere by neighborhoods of a finite number of points (covering basis). Coverings of the unit sphere are used, for example, in non-adaptive polyhedral approximation of multidimensional convex compact bodies based on the evaluation of their support function for directions defined by points of the covering basis. The SSC method is used to iteratively construct a sequence of coverings, each differing from the previous one by a single new point included in the covering basis. Although such coverings are not optimal, it is theoretically shown that they are asymptotically suboptimal. By applying an experimental analysis, the asymptotic efficiency of the SSC method is estimated and the method is shown to be relatively efficient for a small number of points in the covering basis.


49Q20 Variational problems in a geometric measure-theoretic setting
Full Text: DOI