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 en posición convexa independiente si ninguno de los puntos puede representarse como una combinación convexa de los demás.Plantilla:R Un conjunto finito de puntos está en posición convexa si todos ellos son vértices de su envolvente convexa.Plantilla:R 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.Plantilla:R

Propiedades

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.Plantilla:R De manera similar, la triangulación de peso mínimo de conjuntos de puntos planos es NP-duro para conjuntos de puntos arbitrarios, pero se puede resolver en tiempo polinómico mediante programación dinámica para una serie de puntos en posición convexa.Plantilla:R

El teorema de Erdős-Szekeres garantiza que cada conjunto de $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.Plantilla:R Si los puntos $n$ se eligen uniformemente al azar en un cuadrado unidad, la probabilidad de que estén en posición convexa esPlantilla:R

${((\genfrac{}{}{0ex}{}{2n-2}{n-1})/n!)}^2.$

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