On the Complexity of Recognizing Nerves of Convex Sets
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 Rd. 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 Rd, 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.. https://www.cgt-journal.org/index.php/cgt/article/view/40
- Standort
-
Deutsche Nationalbibliothek Frankfurt am Main
- Umfang
-
Online-Ressource
- Sprache
-
Englisch
- Erschienen in
-
On the Complexity of Recognizing Nerves of Convex Sets ; volume:3 ; number:2 ; year:2024
Computing in Geometry and Topology ; 3, Heft 2 (2024)
- Urheber
- DOI
-
10.57717/cgt.v3i2.40
- URN
-
urn:nbn:de:101:1-2023120223311261028302
- Rechteinformation
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Letzte Aktualisierung
-
15.08.2025, 07:37 MESZ
Datenpartner
Deutsche Nationalbibliothek. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Beteiligte
- Schnider, Patrick
- Weber, Simon
Ähnliche Objekte (12)
Set-valued convex analysis
Convex quadrilaterals and k-sets
Rotation Inside Convex Kakeya Sets
Directed Sets and Differences of Convex Compact Sets
Set characterizations and convex extensions for geometric convex-hull proofs
Set characterizations and convex extensions for geometric convex-hull proofs
Tensor products of matrix convex sets
Compact convex sets and boundary integrals
Transversals to Colorful Intersecting Convex Sets
A Combinatorial Property of Convex Sets
On minimal pairs of compact convex sets and of convex functions
Complexity of Secure Sets
Set-valued convex analysis
Convex quadrilaterals and k-sets
Rotation Inside Convex Kakeya Sets
Directed Sets and Differences of Convex Compact Sets
Set characterizations and convex extensions for geometric convex-hull proofs
Set characterizations and convex extensions for geometric convex-hull proofs
Tensor products of matrix convex sets
Compact convex sets and boundary integrals
Transversals to Colorful Intersecting Convex Sets
A Combinatorial Property of Convex Sets
On minimal pairs of compact convex sets and of convex functions
Complexity of Secure Sets
Set-valued convex analysis
Convex quadrilaterals and k-sets
Rotation Inside Convex Kakeya Sets
Directed Sets and Differences of Convex Compact Sets
Set characterizations and convex extensions for geometric convex-hull proofs
Set characterizations and convex extensions for geometric convex-hull proofs
Tensor products of matrix convex sets
Compact convex sets and boundary integrals
Transversals to Colorful Intersecting Convex Sets
A Combinatorial Property of Convex Sets
On minimal pairs of compact convex sets and of convex functions