On the Algorithmic Complexity of Minkowski's Reconstruction Theorem

DOI10.1112/S0024610799007413MaRDI QIDQ3839902zbMATH OpenOpenAlexFDO

Authors Peter Gritzmann, Alexander Hufnagel

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

\(\#\mathbb{P}\)-hardnessapproximationBrunn-Minkowski theorycomputational complexitycomputational convexityconvex bodyconvex programmingdeterministic algorithmextended Gaussian imageimage processingimage reconstructionMinkowski-reconstructionmixed volumesobject recognitionpolynomial-time algorithmpolytopestability theorems

Mathematics Subject Classification ID

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

Review text

In 1903 Minkowski showed that, given pairwise different unit vectors \(u_1,\dots, u_m\) in Euclidean \(n\)-space \(\mathbb{R}^n\) which span \(\mathbb{R}\), and positive reals \(\mu_1,\dots, \mu_m\) such that \(\sum_{i=1}^m \mu_i u_i=0\), there exists a polytope \(P\) in \(\mathbb{R}^n\), unique up to translation, with outer unit facet normals \(u_1,\dots, u_m\) and corresponding facet volumes \(\mu_1,\dots, \mu_m\). The present paper deals with the computational complexity of the underlying reconstruction problem, to determine a presentation of \(P\) as the intersection of its facet halfspaces. After a natural reformulation that reflects the fact that we employ the binary Turing machine model of computation, we show that this reconstruction problem can be solved in polynomial time when the dimension is fixed but is \(\#\mathbb{P}\)-hard when the dimension is part of the input. The problem of `Minkowski reconstruction' has various applications in image processing, and the underlying data structure is relevant for other algorithmic questions in computational convexity.

Recommendations

• Algorithms and Computation
• The complexity of the reconstruction of (r,h,v) from two projections and an approximation algorithm
• Publication:4863381
• scientific article; zbMATH DE number 4211551
• Some results and approaches for reconstruction conjectures
• On the exact maximum complexity of Minkowski sums of polytopes
• scientific article; zbMATH DE number 3906535
• Some work towards the proof of the reconstruction conjecture
• On the computational complexity of reconstructing lattice sets from their X-rays
• On the complexity of graph reconstruction

Cited in

(5)

• Convex set symmetry measurement using Blaschke addition
• A new geometric approach to data analysis using the Minkowski polytope.
• Determining the right-hand vectors of an irredundant linear inequality system
• The complexity of the reconstruction of (r,h,v) from two projections and an approximation algorithm
• On the reverse Loomis-Whitney inequality

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

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