Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls

DOI10.1134/S0965542515100115MaRDI QIDQ904387zbMATH OpenFDO

Authors G. K. Kamenev

Publication date 13 January 2016

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0965542515100115

zbMATH Keywords

computational geometryconvergence rateestimate refinement methodfacial structureHausdorff metricmultidimensional unit ballnumber of facesnumber of verticespolyhedral approximationpolytopes

Mathematics Subject Classification ID

Hausdorff and packing measures (28A78) Approximation by convex sets (52A27) (n)-dimensional polytopes (52B11) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

The author presents new convergence rate estimates of the so-called estimate refinement (ER) method for the polyhedral approximation of the \(d\)-dimensional unit ball \(B^d\) with \(d\geq 3\). The approximation error between a convex polytope and \(B^d\) is measured by the Hausdorff metric. The ER method generates polytopes with an optimal order of growth of the number of vertices and facets on the approximation error. The author estimates the cardinalities of all components of the facial structure of approximating polytopes. It is shown that the number of faces in the polytopes generated by the ER method is asymptotically proportional to the number of their vertices. The convergence rate of the polytopes generated by the ER method is analyzed with respect to the cardinality of facial-structure components. Finally, the new results on the convergence rate of the ER method are compared with former results.

Recommendations

• Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls
• Optimal adaptive methods for the polyhedral approximation of convex bodies
• Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality
• Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball
• Optimal growth order of the number of vertices and facets in the class of Hausdorff methods for polyhedral approximation of convex bodies

Cites work

• A class of adaptive algorithms for approximating convex bodies by polyhedra
• Analysis of an algorithm for approximating convex bodies
• Approximating \(3\)-dimensional convex bodies by polytopes with a restricted number of edges
• Approximation of completely bounded sets by the deep holes method.
• Construction of suboptimal coverings of the multidimensional unit sphere
• Convex Polytopes
• Efficient algorithms for approximation of nonsmooth convex bodies
• scientific article; zbMATH DE number 4212902 (Why is no real title available?)
• scientific article; zbMATH DE number 3690175 (Why is no real title available?)
• scientific article; zbMATH DE number 192896 (Why is no real title available?)
• scientific article; zbMATH DE number 480235 (Why is no real title available?)
• scientific article; zbMATH DE number 1099250 (Why is no real title available?)
• scientific article; zbMATH DE number 1105179 (Why is no real title available?)
• scientific article; zbMATH DE number 2124548 (Why is no real title available?)
• scientific article; zbMATH DE number 3282421 (Why is no real title available?)
• Interactive decision maps. Approximation and visualization of Pareto frontier
• Iterative method for constructing coverings of the multidimensional unit sphere
• Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality
• Numerical analysis of the efficiency of an algorithm for approximating convex bodies by polyhedra
• Optimal adaptive methods for the polyhedral approximation of convex bodies
• Optimal growth order of the number of vertices and facets in the class of Hausdorff methods for polyhedral approximation of convex bodies
• Polytopal approximation bounding the number of \(k\)-faces
• The initial convergence rate of adaptive methods for polyhedral approximation of convex bodies
• The maximum numbers of faces of a convex polytope
• The upper bound theorem for polytopes: An easy proof of its asymptotic version

Cited in

(5)

• Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball
• Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality
• Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls
• The modified method of refined bounds for polyhedral approximation of convex polytopes
• Optimality of the methods for approximating the feasible criterion set in the convex case

This page was built for publication: Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904387)