On the Complexity of Recognizing Nerves of Convex Sets
OPEN ACCESS
Loading...
Author / Producer
Date
2023-11-28
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study the problem of recognizing whether a given abstract simplicial complex K is the k-skeleton of the nerve of j-dimensional convex sets in Rᵈ. We denote this problem by R(k, j, d). As a main contribution, we unify the results of many previous works under this framework and show that many of these works in fact imply stronger results than explicitly stated. This allows us to settle the complexity status of R(1, j, d), which is equivalent to the problem of recognizing intersection graphs of j-dimensional convex sets in Rᵈ, for any j and d. Furthermore, we point out some trivial cases of R(k, j, d), and demonstrate that R(k, j, d) is ER-complete for j in {d - 1, d} and k ≥ d.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
3 (2)
Pages / Article No.
Publisher
Freie Universität Berlin, Institut für Informatik
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Nerve; Recognition; Existential theory of the reals; Intersection graphs
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)