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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .