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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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