Geometric Embeddability of Complexes Is ∃R-Complete

Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in Rd is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d− 1, d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.

Original languageEnglish
Title of host publication39th International Symposium on Computational Geometry, SoCG 2023
Subtitle of host publicationSoCG 2023, June 12-15, 2023, Dallas, Texas, USA
EditorsErin W. Chambers, Joachim Gudmundsson
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Number of pages19
ISBN (Electronic)9783959772730
ISBN (Print)978-3-95977-273-0
Publication statusPublished - 1 Jun 2023

Publication series

NameLeibniz International Proceedings in Informatic
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISSN (Print)1868-8969


  • simplicial complex
  • geometric embedding
  • linear embedding
  • hypergraph
  • recognition
  • existential theory of the reals


Dive into the research topics of 'Geometric Embeddability of Complexes Is ∃R-Complete'. Together they form a unique fingerprint.

Cite this