On the Algorithmic Complexity of Minkowski's Reconstruction Theorem

DOI10.1112/S0024610799007413zbMath0935.52014OpenAlexW1984917688MaRDI QIDQ3839902

Alexander Hufnagel, Peter Gritzmann

Publication date: 10 April 2000

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/s0024610799007413

zbMATH Keywords

computational complexityimage processingapproximationconvex programmingpolytopeconvex bodypolynomial-time algorithmimage reconstructionobject recognitiondeterministic algorithmmixed volumesBrunn-Minkowski theorystability theoremsextended Gaussian imagecomputational convexity\(\#\mathbb{P}\)-hardnessMinkowski-reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) (n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55) Nonlinear programming (90C30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Mixed volumes and related topics in convex geometry (52A39) Data structures (68P05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items (5)

Convex set symmetry measurement using Blaschke addition ⋮ Determining the right-hand vectors of an irredundant linear inequality system ⋮ On the reverse Loomis-Whitney inequality ⋮ A new geometric approach to data analysis using the Minkowski polytope. ⋮ On the reconstruction of convex sets from random normal measurements

This page was built for publication: On the Algorithmic Complexity of Minkowski's Reconstruction Theorem