zbMATH — the first resource for mathematics

On the algorithmic complexity of Minkowski’s reconstruction theorem. (English) Zbl 0935.52014
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.

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