Learning Polytopes with Fixed Facet Directions

DOI10.1137/22M1481695MaRDI QIDQ6161562zbMATH OpenOpenAlexFDO

Authors M. Dostert, Katharina Jochemko

Publication date 27 June 2023

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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

zbMATH Keywords

deformationsleast-squares estimationsupport functionsapproximation of polytopespolyhedral regression

Mathematics Subject Classification ID

Inference from spatial processes (62M30) Learning and adaptive systems in artificial intelligence (68T05) Quadratic programming (90C20) Convex programming (90C25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Convex functions and convex programs in convex geometry (52A41)

Abstract: We consider the task of reconstructing polytopes with fixed facet directions from finitely many support function evaluations. We show that for a fixed simplicial normal fan the least-squares estimate is given by a convex quadratic program. We study the geometry of the solution set and give a combinatorial characterization for the uniqueness of the reconstruction in this case. We provide an algorithm that, under mild assumptions, converges to the unknown input shape as the number of noisy support function evaluations increases. We also discuss limitations of our results if the restriction on the normal fan is removed.

Recommendations

• Numerical reconstruction of convex polytopes from directional moments
• scientific article; zbMATH DE number 175667
• The inverse moment problem for convex polytopes
• Reconstruction of convex bodies from brightness functions

Cites work

• scientific article; zbMATH DE number 3677572 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Convergence of algorithms for reconstructing convex bodies and directional measures
• Convex and Discrete Geometry
• Convex piecewise-linear fitting
• Decomposable convex polyhedra
• Faces of generalized permutohedra
• Fitting tractable convex sets to support function evaluations
• Geometric tomography
• Indecomposable Polytopes
• Lectures on Polytopes
• Multivariate convex regression with adaptive partitioning
• Numerical software to compute Newton polytopes and tropical membership
• On simple polytopes
• Optimal rates of convergence for convex set estimation from support functions
• Permutohedra, Associahedra, and Beyond
• Polytopal Realizations of Generalized Associahedra
• Representations of polytopes and polyhedral sets
• Shape from probing
• Shapes of polyhedra, mixed volumes and hyperbolic geometry
• The maximum numbers of faces of a convex polytope
• The polytope algebra
• The variation of the spectrum of a normal matrix
• Toric varieties
• Triangulations. Structures for algorithms and applications

This page was built for publication: Learning Polytopes with Fixed Facet Directions

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