Computing canonical polyhedra without numerical methods It is well known that every convex polyhedra has a topologically equivalent "canonical form", where its midsphere is precisely the unit sphere centered at the origin, and all the faces are planar.
George Hart has developed an iterative primal-dual numerical method which, given a polyhedron, approximates a canonical form up to arbitrary precision by executing for a large number of iterations. From my experience, it performs well (converges fairly quickly), but this method will still only achieve a numerical approximation.
Does there exist an algorithm which, given a convex polyhedron, can find a canonical form of it with exact locations of the vertices? Can this be done in polynomial time?
 A: I once took a stab at it with Canonical Polyhedra and a related Canonical Polyhedra demo.  
Sometimes I could boil things down to exact vertices when edgelengths converged to rational or quadratic values.
Most of the time, the polyhedra required increasingly large polynomials.  For a few more promising cases I used specialized analysis to figure out the best way to simplify things. High symmetry always helps.
If the edgelengths are all different,  best to give up.  When the edgelengths have some regularity and the general final result is known it's possible to affix exact positions.  For example, the canonical $n$-pyramid has an exact representation, as do the prisms.
The worst 6-sider was the Canonical Tetragonal Antiwedge Hexahedron. It needs order 8 polynomials in the algebraic space of $\sqrt[4]{\phi}$. Not too bad. But for heptahedra I was dealing with order 50 polynomials and up.  
For the hypothetical method without using the numerics first you'd need to give a starting point such as a particular edge with midpoint $(0,0,1)$ and endpoints $(\pm x,0,1)$. From there a heap of simultaneous equations can be set up.  
I'm still struggling with a particular octahedron made with 8 similar polygons with sidelengths $(k^0,k^1,k^0,k^2)$ and $(k^1,k^2,k^1,k^3)$, four of each type. I can't get the simultaneous equations to simplify enough that values for $k$ are produced. The canonical polyhedra get much worse.
