Esta es una publicación cruzada de MathOverflow.
El problema de probar si una red de cara simplicial (informalmente, un grupo de caras) es politopal a veces se llama el problema de Steinitz .
Sturmfels y Bokowski avanzaron un conjunto de métodos a fines de los años 80 para probar si la red reticular de una esfera simplicial también era realizable como un politopo.
El método utiliza matroides orientados. El problema es NP-hard, por lo que su algoritmo requiere un tiempo exponencial en el peor de los casos, pero informaron que el algoritmo a menudo converge rápidamente. Lars Schewe ha demostrado recientemente que el mismo método se puede adaptar para utilizar solucionadores SAT optimizados, aunque la técnica subyacente parece ser la misma.
Tengo curiosidad por saber si se han desarrollado enfoques más nuevos en las décadas intermedias desde que Sturmfels y Bokowski publicaron su resultado. ¿Sigue siendo su método el estado del arte? Además, ¿hay implementaciones de software disponibles que resuelvan este problema, incluso utilizando el enfoque anterior?
En la discusión de MathOverflow, Joe O'Rourke señaló que Polymake tiene una característica que parece calcular realizaciones geométricas de complejos simpliciales [GEOMETRIC_REALIZATION], pero esto no garantiza la politopalidad hasta donde yo sé.
fuente