posición convexa
En geometría discreta y computacional , se dice que un conjunto de puntos en el plano euclidiano o un espacio euclidiano de mayor dimensión están en posición convexa o son convexos independientes 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 los puntos son vértices de su envolvente convexa . [1] Más generalmente, una familia de conjuntos convexosse dice que está en posición convexa si están separados por pares y ninguno de ellos está contenido en el casco convexo de los demás. [2]
Una suposición de posición convexa puede hacer que ciertos problemas computacionales sean más fáciles de resolver. Por ejemplo, el problema del viajante de comercio , NP-difícil para conjuntos arbitrarios de puntos en el plano, es trivial para puntos en posición convexa: el recorrido óptimo es el casco convexo. [3] De manera similar, la triangulación de peso mínimo de conjuntos de puntos planos es NP-difícil para conjuntos de puntos arbitrarios, [4] pero solucionable en tiempo polinomial mediante programación dinámica para puntos en posición convexa. [5]
El teorema de Erdős-Szekeres garantiza que todo conjunto de puntos en posición general (no hay tres en una línea) en dos o más dimensiones tiene al menos un número logarítmico de puntos en posición convexa. [6] Si se eligen puntos uniformemente al azar en un cuadrado unitario , la probabilidad de que estén en posición convexa es [7]
El problema de McMullen pide el número máximo tal que todo conjunto de puntos en posición general en un espacio proyectivo bidimensional tenga una transformación proyectiva a un conjunto en posición convexa. Los límites conocidos son . [8]
