2021/08/05 by Mikkel Abrahamsen, Abrahamsen, Mikkel, Linda Kleist +5
Computer Science · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #General Topology (math.GN) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2108.02585
openalex publication_date 2021/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in \mathbb Rd is complete for the Existential Theory of the Reals for all d≥ 3 and k∈\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.