Posición convexa
# Posición convexa

En geometría discreta y en geometría computacional, se dice que un conjunto de puntos en el plano o en un espacio euclídeo de dimensiones superiores está en posición convexa o convexa independiente si ninguno de los puntos puede representarse como una combinación convexa de los demás. Un conjunto finito de puntos está en posición convexa si todos los puntos son vértices de su envolvente convexa. De manera más general, se dice que una familia de convexidades está en posición convexa si están separadas por pares y ninguno de ellos está contenido en la envolvente convexa de los demás.

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 el casco convexo. De manera similar, el triangulación de peso mínimo de conjuntos de puntos planos es NP-duro para conjuntos de puntos arbitrarios, pero se puede resolver en complejidad temporal mediante programación dinámica para puntos en posición convexa.

El Teorema de Erdős-Szekeres garantiza que cada conjunto de puntos $n$ en posición general (no tres en línea) en dos o más dimensiones tenga al menos un número logarítmico de puntos en posición convexa. Si los puntos $n$ se eligen uniformemente al azar en un cuadrado unidad, la probabilidad de que estén en posición convexa es

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

El McMullen problem solicita el número máximo $\nu (d)$ tal que cada conjunto de puntos $\nu (d)$ en posición general en un $d$ dimensional espacio proyectivo tenga un homografía (geometría) para un conjunto en posición convexa. Los límites conocidos son $2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil$.

