Skip to main content
5 of 10
added 93 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

A simple query on John's ellipsoid and symmetry of polytope?

Suppose we have a convex polyhedron in $\Bbb R^n$ symmetric then we know there is an unique ellipsoid of maximum volume called John's ellipsoid inscribed in it.

  1. Do I need all the vertices of the polytope to determine the ellipsoid or getting an uniform sample of $O(n^c)$ vertices for some fixed $c>0$ suffices to approximate the ellipsoid upto $\epsilon$ factor in each axis provided we know that the barycenter agrees with center of the ellipsoid and we know the center within some neighborhood?

I am asking this since the ellipsoid has only $O(n^2)$ parameters.


UPDATE: How about if I sample faces instead of vertices. Would $O(n^c)$ random $2$-faces suffice?

Turbo
  • 13.9k
  • 1
  • 27
  • 76