Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality
Georgy K. Kamenev · Computational Mathematics and Mathematical Physics · 2014
The problem of polyhedral approximation of a multidimensional ball is considered. It is well known that the norm of the f-vector (the maximum number of faces of all dimensions) of an approximating polytope grows at least as fast as O(δ(1 − d)/2), where δ is the Hausdorff deviation and d is the space dimension. An iterative method, namely, the deep holes method is used to construct metric nets. As applied to the problem under study, the method sequentially supplements the vertex set of the polytope with its deep holes in the metric on the ball surface (i.e., with points of the surface that are farthest away from the vertices of the polytope). It is shown that the facet structure cardinality of the constructed polytope has an optimal growth rate. It is also shown that the number of faces of all dimensions in the approximating polytopes generated by the method is asymptotically proportional to the number of their vertices. Closed-form expressions for the constants are obtained, which depend only on the dimension of the space, including the case of high dimensions. For low dimensions (d ranging from 3 to 5), upper bounds for the growth rate of the number of faces of all dimensions are obtained depending on the accuracy of the approximation.