Decidir la pertenencia a un casco convexo

Question

Puntos determinados $u, v_1, \dots,v_n \in \mathbb{R}^m$ decida si $u$ está contenido en el casco convexo de $v_1, \dots, v_n$ .

Esto puede hacerse eficientemente mediante programación lineal (tiempo polinomial en $n,m$ ) de la forma obvia. Tengo dos preguntas:

1. ¿Hay algún algoritmo diferente (o más eficaz) para esto? Si no es así, también debería haber una reducción sencilla de la programación lineal al problema anterior. ¿De qué se trata?

2. ¿Existen familias interesantes de instancias para las que el problema pueda resolverse significativamente más rápido que mediante programación lineal, por ejemplo, tiempo casi lineal en $m+n$ .

Answer 1

No es sólo que se pueda resolver el problema con programación lineal. En realidad, la reducción a la programación lineal muestra que el problema del casco convexo es equivalente, por dualización, al problema del punto factible en la programación lineal. En otras palabras, se pregunta si existen coeficientes $\alpha_1,\ldots,\alpha_n \ge 0$ tal que $$u = \alpha_1 v_1 + \alpha_2 v_2 + \cdots + \alpha_n v_n.$$ El vector de coeficientes $\vec{\alpha}$ es un punto factible en un problema general de programación lineal, y usted se pregunta si existe un punto factible. Por lo tanto, el problema no puede ser ni más difícil ni más fácil que la programación lineal.

Su segunda pregunta se refiere a si existen casos especiales de (el problema del punto factible de) la programación lineal que sean más fáciles que el caso general de la programación lineal. La respuesta es afirmativa. Por ejemplo, el algoritmo de tipo "quickhull" que menciona Steve Huntsman funciona bien en cualquier dimensión baja específica. Equivale a un algoritmo de programación lineal para el caso de que los coeficientes sean no negativos y haya pocas igualdades. También se puede esperar un algoritmo más rápido (tal vez incluso equivalente a quickhull) en el otro extremo, cuando hay casi tantas igualdades como variables. Y siempre se puede pensar en nuevos tipos de problemas de programación lineal estructurada que sean más convenientes o más rápidos, por ejemplo, con una matriz dispersa.

Answer 2

Quickhull utiliza divide y vencerás a la ordenación rápida . Creo que su complejidad en el peor de los casos es $O(n^2)$ pero podría estar equivocado.

Answer 3

"¿Existen familias interesantes de instancias... de tiempo casi lineal..."

Para que conste, cabe mencionar que si los puntos $v_1,\ldots,v_n \in \mathbb{R}^d$ se eligen aleatoriamente, bajo una variedad de distribuciones y dentro de un variedad de regiones (por ejemplo, bolas, hipercubos), entonces el número de vértices del casco es $O(n^{1/3})$ en el plano y $O(\log^{d-1}n)$ en dimensión $d$ .

Una referencia reciente, que cita muchos de los trabajos originales es:

Sariel Har-Peled, "Sobre la complejidad esperada de cascos convexos aleatorios". 2011. ( Enlace al resumen de arXiv ).