How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914163864895488 |
|---|---|
| author | Schaefer, Marcus Štefankovič, Daniel |
| author_facet | Schaefer, Marcus Štefankovič, Daniel |
| contents | A set is star-shaped if there is a point in the set that can see every other point in the set in the sense that the line-segment connecting the points lies within the set. We show that testing whether a non-empty compact smooth region is star-shaped is $\forall\mathbb{R}$-complete. Since the obvious definition of star-shapedness has logical form $\exists\forall$, this is a somewhat surprising result, based on Krasnosel'ski\uı's theorem from convex geometry; we study several related complexity classifications in the real hierarchy based on other results from convex geometry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18818 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How Hard is it to be a Star? Convex Geometry and the Real Hierarchy Schaefer, Marcus Štefankovič, Daniel Computational Geometry Computational Complexity 68Q17, 52-08 A set is star-shaped if there is a point in the set that can see every other point in the set in the sense that the line-segment connecting the points lies within the set. We show that testing whether a non-empty compact smooth region is star-shaped is $\forall\mathbb{R}$-complete. Since the obvious definition of star-shapedness has logical form $\exists\forall$, this is a somewhat surprising result, based on Krasnosel'ski\uı's theorem from convex geometry; we study several related complexity classifications in the real hierarchy based on other results from convex geometry. |
| title | How Hard is it to be a Star? Convex Geometry and the Real Hierarchy |
| topic | Computational Geometry Computational Complexity 68Q17, 52-08 |
| url | https://arxiv.org/abs/2506.18818 |