Geometric Embeddability of Complexes is $\exists \mathbb R$-complete
Preprint
Abstract
We show that the decision problem of determining whether a given (abstract simplicial) $k$-complex has a geometric embedding in $\mathbb R^d$ is complete for the Existential Theory of the Reals for all $d\geq 3$ and $k\in\{d-1,d\}$. This implies that the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution. Moreover, this implies NP-hardness and constitutes the first hardness results for the algorithmic problem of geometric embedding (abstract simplicial) complexes.
Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- The Complexity of Drawing a Graph in a Polygonal Region2018
- Recognition and Complexity of Point Visibility GraphsDiscrete & Computational Geometry, 2016
- Extendability of Continuous Maps Is UndecidableDiscrete & Computational Geometry, 2013
- Complexity of Some Geometric and Topological Problems2010
- A History of Algebraic and Differential Topology, 1900 - 19602009
- Necessary Conditions for Geometric Realizability of Simplicial Complexes2008
- A Note on Geometric Embeddings of Simplicial Complexes in a Euclidean SpaceDiscrete & Computational Geometry, 2000
- Realization Spaces of Polytopes1996
- The universality theorems on the classification problem of configuration varieties and convex polytopes varieties1988
- Knots and links in spatial graphsJournal of Graph Theory, 1983