Optimal non-adaptive approximation of convex bodies by polytopes

DOI10.1007/978-3-030-23436-2_11zbMATH Open1442.52005arXiv1810.12098OpenAlexW2898098839MaRDI QIDQ5114895FDOQ5114895

Authors: G. K. Kamenev 

Publication date: 29 June 2020

Published in: Lecture Notes in Computational Science and Engineering (Search for Journal in Brave)

Abstract: In this paper we consider the problem of constructing numerical algorithms for approximating of convex compact bodies in d-dimensional Euclidean space by polytopes with any given accuracy. It is well known that optimal with respect to the order algorithms produces polytopes for which the accuracy in Hausdorff metric is inversely proportional to the number of vertices (faces) in the degree of 2/(d-1). Numerical approximation algorithms can be adaptive (active) when the vertices or faces are constructed successively, depending on the information obtained in the process of approximation, and non-adaptive (passive) when parameters of algorithms are defined on the basis of a priory information available. Approximation algorithms differ in the use of operations applied to the approximated body. Most common are indicator, support and distance (Minkowski) functions calculations. Some optimal active algorithms for arbitrary bodies approximation are known using support or distance function calculation operation. Optimal passive algorithms for smooth bodies approximation are known using support function calculation operation and extremal curvature information. It is known that there are no optimal non-adaptive algorithms for arbitrary bodies approximation using support function calculation operation. We consider optimal non-adaptive algorithms for arbitrary bodies approximation using projection function calculation operation.

Full work available at URL: https://arxiv.org/abs/1810.12098

Recommendations

• scientific article; zbMATH DE number 2208569
• Analysis of an algorithm for approximating convex bodies
• Efficient algorithms for approximation of nonsmooth convex bodies
• scientific article; zbMATH DE number 2048740
• scientific article; zbMATH DE number 665688

zbMATH Keywords

approximation of convex bodies by polytopesoptimal non-adaptive algorithms

Mathematics Subject Classification ID

Approximation by convex sets (52A27) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Cites Work

• Interactive decision maps. Approximation and visualization of Pareto frontier
• Title not available (Why is that?)
• Title not available (Why is that?)
• Construction of suboptimal coverings of the multidimensional unit sphere
• Numerical analysis of the efficiency of an algorithm for approximating convex bodies by polyhedra
• 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
• Efficient algorithms for approximation of nonsmooth convex bodies
• Approximation of convex sets by polytopes
• Metric entropy of some classes of sets with differentiable boundaries
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 10.1007/s11470-008-3005-z
• Efficient algorithms for approximation of nonsmooth convex bodies
• Optimal adaptive methods for the polyhedral approximation of convex bodies
• Title not available (Why is that?)

This page was built for publication: Optimal non-adaptive approximation of convex bodies by polytopes

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