Algoritmos más rápidos para cascos convexos

Question

Me interesaba lo siguiente:

Dados dos poliedros $P_1, P_2$ especificado en el formulario:

$$ P_1 = \{x : A_1x \le b_1 \} $$ $$ P_2 = \{x : A_2x \le b_2 \} $$

Mientras que $x \in R^n$ y $b_1, b_2$ son vectores reales de la misma dimensión "altura" que $P_1$ y $P_2$ respectivamente.

¿Cómo se determina el casco convexo $C$ de estos dos poliedros. Dado en la forma

$$ C = \{ x : Qx \le \tau \} $$

Mientras que $Q, \tau$ debe ser el número mínimo de inecuaciones necesarias para especificar el conjunto.

Había publicado esta pregunta en Intercambio OR que recomendaba la eliminación de Fourier-Motzkin junto con un esquema sencillo para incluir todos los puntos en la carcasa.

Mi único reparo es que esto duplicó el número de variables. Y ejecutar Fourier-Motzkin llevaría un tiempo exponencial para reducir el "exceso" de variables.

¿Existe algún procedimiento que no requiera un tiempo exponencial y que mantenga el mismo número de variables?

Answer 1

No, no creo que se pueda encontrar un algoritmo rápido garantizado, ya que el problema parece intratable en general, si he entendido bien el documento de abajo. Una búsqueda rápida me llevó, por ejemplo, a

Sobre la dificultad de calcular la intersección, la unión y la suma de Minkowski de Politopos, por Hans Raj Tiwary

Answer 2

No se puede evitar un aumento exponencial del número de restricciones resultantes.

Como ejemplo, veamos el politopo cruzado $P_3$ en $\mathbb{R}^n$ . Es el casco convexo de todos los vértices obtenidos por todas las permutaciones de $(\pm1,0,\dots,0)$ . Por lo tanto, tiene $2n$ vértices y $2^n$ facetas (ver https://en.wikipedia.org/wiki/Cross-polytope ) y su $\mathcal{H}$ -representación $Qx \leq \tau$ tiene al menos $2^n$ filas. Por otro lado, los dos símiles $P_1$ y $P_2$ , donde $$P_1 = conv\{(0,\dots,0), (1,0,\dots,0), (0,1,0,\dots,0), \dots, (0,\dots,0,1)\}$$ $$P_2 = conv\{(0,\dots,0), (-1,0,\dots,0), (0,-1,0,\dots,0), \dots, (0,\dots,0,-1)\},$$ tienen $n+1$ vértices y también $n+1$ facetas. Por lo tanto, su (mínimo) $\mathcal{H}$ -representaciones $A_1x \leq b_1$ y $A_2x \leq b_2$ tienen $n+1$ filas cada una. Es crucial observar que el casco convexo de $P_1$ y $P_2$ es exactamente el politopo cruzado $P_3$ . Esto demuestra que en su entorno (a menos que me haya perdido algo sobre la "aplicación específica") es imposible tener un procedimiento que no tome un tiempo exponencial en el peor de los casos.