3
$\begingroup$

A centrally symmetric convex polyhedron in $\Bbb R^n$ shifted from the origin with possibly $e^{\alpha n}$ number of vertices at some $\alpha>0$ has an unique ellipsoid of maximum volume called John's ellipsoid inscribed in it with barycenter of the polyhedron agreeing with center of the ellipsoid.

Obtain an uniform sample of $O(n^c)$ vertices at some fixed $c\geq2$.

  1. Can we apply central limit theorem to approximate barycenter by mean of sample vertices?

  2. Since ellipsoids have only $O(n^2)$ parameters does this sample give a constant fraction approximation of each axis to the ellipsoid?

Improve this question
$\endgroup$
4
  • $\begingroup$ so why negative vote? $\endgroup$
    – Turbo
    Commented May 12, 2017 at 19:43
  • 3
    $\begingroup$ (Not the downvote, but) I think your question is unclear, at least to me. Specifically what does it mean for the convex hull of some vertices of the polytope to "determine" the ellipsoid. Can you provide an example? $\endgroup$
    – Yoav Kallus
    Commented May 12, 2017 at 19:50
  • $\begingroup$ @YoavKallus clarified. $\endgroup$
    – Turbo
    Commented May 12, 2017 at 20:01
  • $\begingroup$ It seems to me that the $k=O(n^2)$ parameters that determine an ellipsoid can be achieved by $k$ facets tangent to the ellipsoid. So your question is easier to answer in terms of facets than in terms of vertices. One could certainly dispense with all the vertices that are not incident to a facet tangent to the ellipsoid. $\endgroup$
    – Joseph O'Rourke
    Commented May 12, 2017 at 20:14

1 Answer 1

Reset to default
2
$\begingroup$

No, a fixed number of added vertices can change the John ellipsoid by an arbitrary amount when added to arbitrarily many already known vertices: consider a very thin regular n-gon prism centered about the origin. Now we can add two new vertices in a way that doesn't change the polyhedron much (near existing vertices, say), or we can add two new vertices along the axis of the prism very far away from it (in a symmetric way, so that the polyhedron is still centered about the origin). The two possibilities have very different John ellipsoids, so you cannot approximate the John ellipsoid before knowing where these vertices are.

If you are sampling the vertices uniformly at random, then you have a good chance of missing the two crucial ones out of the many noncrucial ones.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes. But I am sampling a centrally symmetric polytope which already has a structure. So the drastic changes you suggest may be unlikely event. right? $\endgroup$
    – Turbo
    Commented May 13, 2017 at 1:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .