6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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