Determining Inscribability of Polytopes via Rank Minimization Based on Slack Matrices
SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 680-705
DOI: 10.1137/25m1731460 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 12.05.2026. Verfasst von Yiwen Chen und 3 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, Centro de Matemática da Universidade de Coimbra.
Abstract (Originalsprache)
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 a semidefinite programming (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 [Formula: see text] with vertices [Formula: see text], revealing its potential in high dimensions.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- Centro de Matemática da Universidade de Coimbra
Zitieren
APA
Chen, Y., Gouveia, J., Hare, W., & Wiebe, A. (2026). Determining Inscribability of Polytopes via Rank Minimization Based on Slack Matrices. SIAM Journal on Discrete Mathematics, 40(2), 680-705. https://doi.org/10.1137/25m1731460
Vancouver
Chen Y, Gouveia J, Hare W, Wiebe A. Determining Inscribability of Polytopes via Rank Minimization Based on Slack Matrices. SIAM Journal on Discrete Mathematics. 2026;40(2):680-705. doi:10.1137/25m1731460
BibTeX
@article{Chen2026,
author = {Chen, Yiwen and Gouveia, João and Hare, Warren and Wiebe, Amy},
title = {Determining Inscribability of Polytopes via Rank Minimization Based on Slack Matrices},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {2},
pages = {680--705},
doi = {10.1137/25m1731460}
}
EUVIMED