Radii minimal projections of polytopes and constrained optimization of symmetric polynomials

DOI10.1515/ADVGEOM.2006.005MaRDI QIDQ5488627zbMATH OpenOpenAlexFDO

Authors René Brandenberg, Thorsten Theobald

Publication date 22 September 2006

Published in advg (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(11)

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

Describes a project that uses

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)