Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a theorem of Minkowski that says that given $k$ unit vectors $x_i$ that span $\mathbb{R}^n$ and $k$ positive real numbers $a_i$ such that $\sum_{i=0}^k a_i x_i = 0$ then there exists a unique convex polytope (up to translation) such that the $i$th face is normal to $x_i$ and has area ($n-1$ dimensional volume) $a_i$. Does there exist an algorithm constructing this polytope?

In theory it should be straightforward as the area of each face is a piecewise polynomial function of the positions of the half planes describing the other faces. Unfortunately these functions appear to be somewhat problematic to derive, let alone simultaneously solve.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

This was first examined in an old (1985) but very good paper on this question, just in $\mathbb{R}^3$: James Little, "Determining object attitude from extended Gaussian images," CiteSeer link, Symposium on Computational Geometry link. Then a decade later, Peter Gritzmann and Hufnagel published a solution in the same proceedings, for polytopes in arbitrary dimension: "A polynomial time algorithm for Minkowski reconstruction," Symposium on Computational Geometry link. This eventually became "On the Algorithmic Complexity of Minkowski's Reconstruction Theorem," Journal London Mathematical Society, Volume59, Issue3, Pp. 1081-1100:

[I]t is shown that this reconstruction problem can be solved in polynomial time when the dimension is fixed but is #P-hard when the dimension is part of the input.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.