TY - JOUR

T1 - On the algorithmic complexity of Minkowski's reconstruction theorem

AU - Gritzmann, Peter

AU - Hufnagel, Alexander

N1 - Funding Information:
Research of the first author was supported in part by the Alexander von Humboldt Foundation and by a Max Planck Research Award. Research of both authors was supported in part by Deutsche Forschungsgemeinschaft grants GR 993}3-1 and GR 993}3-2.

PY - 1999/6

Y1 - 1999/6

N2 - In 1903 Minkowski showed that, given pairwise different unit vectors u1, ... ,um in Euclidean n-space ℝn which span ℝn, and positive reals μ1, ... ,μm such that Σmi=1μiui = 0, there exists a polytope P in ℝn, unique up to translation, with outer unit facet normals u1, ...,um and corresponding facet volumes μ1, ...,μm. This 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 the binary Turing-machine model of computation is employed, it is shown that this reconstruction problem can be solved in polynomial time when the dimension is fixed but is #ℙ-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.

AB - In 1903 Minkowski showed that, given pairwise different unit vectors u1, ... ,um in Euclidean n-space ℝn which span ℝn, and positive reals μ1, ... ,μm such that Σmi=1μiui = 0, there exists a polytope P in ℝn, unique up to translation, with outer unit facet normals u1, ...,um and corresponding facet volumes μ1, ...,μm. This 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 the binary Turing-machine model of computation is employed, it is shown that this reconstruction problem can be solved in polynomial time when the dimension is fixed but is #ℙ-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.

UR - http://www.scopus.com/inward/record.url?scp=0000797533&partnerID=8YFLogxK

U2 - 10.1112/S0024610799007413

DO - 10.1112/S0024610799007413

M3 - Article

AN - SCOPUS:0000797533

SN - 0024-6107

VL - 59

SP - 1081

EP - 1100

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

IS - 3

ER -