Radii minimal projections of polytopes and constrained optimization of symmetric polynomials

DOI10.1515/ADVGEOM.2006.005zbMATH Open1108.52010arXivmath/0311017OpenAlexW2962732036MaRDI QIDQ5488627FDOQ5488627

Authors: René Brandenberg, Thorsten Theobald 

Publication date: 22 September 2006

Published in: advg (Search for Journal in Brave)

Abstract: We provide a characterization of the radii minimal projections of polytopes onto $j$-dimensional subspaces in Euclidean space $E^n$. Applied on simplices this characterization allows to reduce the computation of an outer radius to a computation in the circumscribing case or to the computation of an outer radius of a lower-dimensional simplex. In the second part of the paper, we use this characterization to determine the sequence of outer $(n-1)$-radii of regular simplices (which are the radii of smallest enclosing cylinders). This settles a question which arose from the incidence that a paper by Wei{ss}bach (1983) on this determination was erroneous. In the proof, we first reduce the problem to a constrained optimization problem of symmetric polynomials and then to an optimization problem in a fixed number of variables with additional integer constraints.

Full work available at URL: https://arxiv.org/abs/math/0311017

Recommendations

• Radii of simplices and some applications to geometric inequalities
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• Über Umkugeln von Projektionen regulärer Simplexe
• Radii of regular polytopes
• The largest projections of regular polytopes

zbMATH Keywords

polynomial optimizationprojectionpolytopesymmetric polynomialsregular simplexouter radiusenclosing cylinder

Mathematics Subject Classification ID

Semidefinite programming (90C22) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) (n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Cites Work

• Global optimization with polynomials and the problem of moments
• GloptiPoly
• Semidefinite programming relaxations for semialgebraic problems
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Optimization of Polynomials on Compact Semialgebraic Sets
• Deterministic and randomized polynomial‐time approximation of radii
• Smallest enclosing cylinders
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces
• Radii of regular polytopes
• Algebraic methods for computing smallest enclosing and circumscribing cylinders of simplices
• Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces
• High-dimensional shape fitting in linear time

Cited In (11)

• About the algebraic solutions of smallest enclosing cylinders problems
• Fitting enclosing cylinders to data in \(\mathbb R^n\)
• Intrinsic volumes and successive radii
• Classification of the congruent embeddings of a tetrahedron into a triangular prism
• Regular simplices passing through holes
• On the families of successive radii and the sum of convex sets
• Radii of regular polytopes
• Projection minima of a symmetric convex body
• Successive radii and Minkowski addition
• Plus minus analogues for affine Tverberg type results
• Holding a regular pyramid by a circle

Uses Software

• GloptiPoly

This page was built for publication: Radii minimal projections of polytopes and constrained optimization of symmetric polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5488627)