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. Un conjunto finito de puntos está en posición convexa si todos ellos 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 ninguna de ellas está contenida en la envolvente convexa de las demás.
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. 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.
El teorema de Erdős-Szekeres garantiza que cada conjunto de 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. Si los puntos se eligen uniformemente al azar en un cuadrado unidad, la probabilidad de que estén en posición convexa es
El problema de McMullen consiste en hallar el número máximo tal que cada conjunto de puntos en posición general en un espacio proyectivo -dimensional tenga una transformación proyectiva que genere un conjunto imagen en posición convexa. Los límites conocidos son .
Referencias
Categoría:Envolventes convexas