Posición convexa , la enciclopedia libre

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 en posición convexa independiente si ninguno de los puntos puede representarse como una combinación convexa de los demás.^[1]​ Un conjunto finito de puntos está en posición convexa si todos ellos son vértices de su envolvente convexa.^[1]​ De manera más general, se dice que una familia de convexidades está en posición convexa si están separadas por pares y ninguna de ellas está contenida en la envolvente convexa de las demás.^[2]​

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]​