Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball (Q2278205)

The problem of comparing methods for approximating convex compact bodies by double description polytopes is formulated in terms of comparing the complexity of approximation techniques. First of all, a technique of approximating a ball by double description best approximation polytopes is described and its complexity is studied. Second, a ball is approximated by another method based on a double description polytope with vertices at nodes of a nonadaptive net. The third approach in case of approximating a ball consists in describing the Estimate Refinement method in terms of operations for which the computational complexity can be estimated. The three techniques of approximation are finally compared from the complexity point of view.