Algoritmo constructivo para el teorema de Minkowski.

Question

Hay un teorema de Minkowski que dice que dado $k$ vectores unitarios $x_i$ que abarcan $\mathbb{R}^n$ y $k$ números reales positivos $a_i$ tal que $\sum_{i=0}^k a_i x_i = 0$ entonces existe un único politopo convexo (hasta la traslación) tal que el $i$ La cara es normal para $x_i$ y tiene un área ( $n-1$ volumen dimensional) $a_i$ . ¿Existe un algoritmo que construya este politopo?

En teoría, debería ser sencillo, ya que el área de cada cara es una función polinómica a trozos de las posiciones de los semiplanos que describen las otras caras. Desgraciadamente, estas funciones parecen ser algo problemáticas de derivar, y mucho menos de resolver simultáneamente.

Answer 1

Esto se examinó por primera vez en un documento antiguo (1985) pero muy bueno sobre esta cuestión, justo en $\mathbb{R}^3$ : James Little, "Determinación de la actitud del objeto a partir de imágenes gaussianas extendidas". Enlace a CiteSeer , Simposio sobre Geometría Computacional enlace . Luego, una década más tarde, Peter Gritzmann y Hufnagel publicaron una solución en el mismos procedimientos, para politopos de dimensión arbitraria: "Un algoritmo de tiempo polinómico para la reconstrucción de Minkowski". Simposio sobre Geometría Computacional enlace . Esto se convirtió finalmente en "Sobre la complejidad algorítmica del teorema de reconstrucción de Minkowski". Revista de la Sociedad Matemática de Londres Volumen 59, número 3, págs. 1081-1100 :

[Se demuestra que este problema de reconstrucción puede resolverse en tiempo polinómico cuando la dimensión es fija pero es #P-difícil cuando la dimensión es parte de la entrada.