Suppose I have an abstract polytope defined by a poset. Are there any methods for determining whether the abstract polytope can be geometrically realized as convex-hull on its set of vertices?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ This is called the "Steinitz problem". See mathematik.tu-darmstadt.de/~pfetsch/apropo/… $\endgroup$– Hugh ThomasCommented Aug 21, 2014 at 1:26
Add a comment
|
1 Answer
$\begingroup$
Quote from the Handbook of Discrete and Computational Geometry, 2nd Edition, p.370.
$\endgroup$
1
You may be interested in this negative result, which shows the space of realizations of an abstract $4$-polytope may be arbitrarily wild:
Quote from the Handbook of Discrete and Computational Geometry, 2nd Edition, p.370.
As the link Hugh Thomas provided indicates, Richter-Gebert also proved that determining whether an abstract polytope is realizable is NP-hard for fixed dimensions $d \ge 4$.
answered Aug 21, 2014 at 1:20
-
2$\begingroup$ While Joseph O'Rourke is right that the general case is probably tricky, one can do something in more restrictive settings: For $d=3$ Steinitz' theorem tells you if your abstract graph is actually the graph of a convex $3$-polytope. If this is the case you know that your abstract polytope is realizable. For the $d$-dimensional case there exists Friedman's algorithm that allows you to reconstruct a simple polytope from its graph in polynomial time (based on results by Blind & Mani and Kalai). Maybe this can be used to decide if an abstract simple polytope is realizable. $\endgroup$– eins6180Commented Aug 22, 2014 at 7:17