1
$\begingroup$
  1. Do the symmetry group generators of a regular convex polytope and a marked $\{0,1\}^n$ vertex point suffice to embed the polytope uniquely with $\{0,1\}^n$ vertex set?

  2. If so can we find the John's ellipsoid of this polytope in polynomial time?

$\endgroup$

1 Answer 1

1
$\begingroup$

I am not sure I understand the question: if you know a vertex, and the symmetry group generators, and the symmetry group is transitive on the vertex set, don't you know all the vertices? And then your polytope is just the convex hull?

As for the second question, in sufficiently high dimensions the only regular polytopes are the regular simplex, the regular cube, and the regular co-cube ("hyperoctahedron"). In all cases, the John ellipsoid is a ball (the inscribed ball). The inscribed ball of a simplex is linear algebra and not at all difficult, the cube has to be the whole $\{0, 1\}^n,$ so that's not hard either. For the hyperoctahedron, there are only $2 d$ vertices, so finding two opposite faces is not so hard.

For dimensions $3, 4$ there are finitely many possibilities.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.