The Complexity of Recognizing Geometric Hypergraphs
share
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hypergraph H=(V,E), each vertex v∈ V is associated with a point p_v∈ℝ^d and each hyperedge e∈ E is associated with a connected set s_e⊂ℝ^d such that {p_v| v∈ V}∩ s_e={p_v| v∈ e} for all e∈ E. We say that a given hypergraph H is representable by some (infinite) family F of sets in ℝ^d, if there exist P⊂ℝ^d and S ⊆ F such that (P,S) is a geometric representation of H. For a family F, we define RECOGNITION(F) as the problem to determine if a given hypergraph is representable by F. It is known that the RECOGNITION problem is ∃ℝ-hard for halfspaces in ℝ^d. We study the families of translates of balls and ellipsoids in ℝ^d, as well as of other convex sets, and show that their RECOGNITION problems are also ∃ℝ-complete. This means that these recognition problems are equivalent to deciding whether a multivariate system of polynomial equations with integer coefficients has a real solution.
READ FULL TEXT