Determining inscribability of polytopes via rank minimization based on slack matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916007612776448 |
|---|---|
| author | Chen, Yiwen Gouveia, João Hare, Warren Wiebe, Amy |
| author_facet | Chen, Yiwen Gouveia, João Hare, Warren Wiebe, Amy |
| contents | A polytope is inscribable if there is a realization where all vertices lie on the sphere. In this paper, we provide a necessary and sufficient condition for a polytope to be inscribable. Based on this condition, we characterize the problem of determining inscribability as a minimum rank optimization problem using slack matrices. We propose an SDP approximation for the minimum rank optimization problem and prove that it is tight for certain classes of polytopes. Given a polytope, we provide three algorithms to determine its inscribability. All the optimization problems and algorithms we propose in this paper depend on the number of vertices and facets but are independent of the dimension of the polytope. Numerical results demonstrate our SDP approximation's efficiency, accuracy, and robustness for determining inscribability of simplicial polytopes of dimensions $4\le d\le 8$ with vertices $n\le 10$, revealing its potential in high dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01878 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Determining inscribability of polytopes via rank minimization based on slack matrices Chen, Yiwen Gouveia, João Hare, Warren Wiebe, Amy Combinatorics Optimization and Control 52B12, 52B55, 90C22 A polytope is inscribable if there is a realization where all vertices lie on the sphere. In this paper, we provide a necessary and sufficient condition for a polytope to be inscribable. Based on this condition, we characterize the problem of determining inscribability as a minimum rank optimization problem using slack matrices. We propose an SDP approximation for the minimum rank optimization problem and prove that it is tight for certain classes of polytopes. Given a polytope, we provide three algorithms to determine its inscribability. All the optimization problems and algorithms we propose in this paper depend on the number of vertices and facets but are independent of the dimension of the polytope. Numerical results demonstrate our SDP approximation's efficiency, accuracy, and robustness for determining inscribability of simplicial polytopes of dimensions $4\le d\le 8$ with vertices $n\le 10$, revealing its potential in high dimensions. |
| title | Determining inscribability of polytopes via rank minimization based on slack matrices |
| topic | Combinatorics Optimization and Control 52B12, 52B55, 90C22 |
| url | https://arxiv.org/abs/2502.01878 |