Approximations of convex bodies by polytopes and by projections of spectrahedra
From MaRDI portal
Publication:6232047
Semidefinite programming (90C22) Computational aspects related to convexity (52B55) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Approximation by convex sets (52A27)
Abstract: We prove that for any compact set B in R^d and for any epsilon >0 there is a finite subset X of B of |X|=d^{O(1/epsilon^2)} points such that the maximum absolute value of any linear function ell: R^d --> R on X approximates the maximum absolute value of ell on B within a factor of epsilon sqrt{d}. We also discuss approximations of convex bodies by projections of spectrahedra, that is, by projections of sections of the cone of positive semidefinite matrices by affine subspaces.
This page was built for publication: Approximations of convex bodies by polytopes and by projections of spectrahedra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232047)
