Posición convexa

La suposición de una posición convexa puede facilitar la resolución de ciertos problemas computacionales. Por ejemplo, el problema del viajante, NP-duro para conjuntos arbitrarios de puntos en el plano, es trivial para puntos en posición convexa: el recorrido óptimo es la envolvente convexa.^[3]​ De manera similar, la triangulación de peso mínimo de conjuntos de puntos planos es NP-duro para conjuntos de puntos arbitrarios,^[4]​ pero se puede resolver en tiempo polinómico mediante programación dinámica para una serie de puntos en posición convexa.^[5]​

El teorema de Erdős-Szekeres garantiza que cada conjunto de ${\displaystyle n}$ puntos en posición general (excepto para tres o más de ellos en línea recta) en dos o más dimensiones tenga al menos un número logarítmico de puntos en posición convexa.^[6]​ Si los puntos ${\displaystyle n}$ se eligen uniformemente al azar en un cuadrado unidad, la probabilidad de que estén en posición convexa es^[7]​

${\displaystyle \left({\binom {2n-2}{n-1}}/n!\right)^{2}.}$

El problema de McMullen consiste en hallar el número máximo ${\displaystyle \nu (d)}$ tal que cada conjunto de ${\displaystyle \nu (d)}$ puntos en posición general en un espacio proyectivo ${\displaystyle d}$ -dimensional tenga una transformación proyectiva que genere un conjunto imagen en posición convexa. Los límites conocidos son ${\displaystyle 2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil }$ . ^[8]​