Posición convexa

En geometría discreta y computacional, se dice que un conjunto de puntos en el plano euclidiano o en un espacio euclidiano de dimensión superior está en posición convexa o es convexamente 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 los puntos son vértices de su envolvente convexa . ^{[ 1 ]} De manera más general, se dice que una familia de conjuntos convexos está en posición convexa si son disjuntos dos a dos y ninguno de ellos está contenido en la envolvente convexa de los demás. ^{[ 2 ]}

Suponer una posición convexa puede facilitar la resolución de ciertos problemas computacionales. Por ejemplo, el problema del viajante , NP-difícil para conjuntos arbitrarios de puntos en el plano, es trivial para puntos en posición convexa: el recorrido óptimo es la envoltura convexa. ^{[ 3 ]} De manera similar, la triangulación de peso mínimo de conjuntos de puntos planares es NP-difícil para conjuntos de puntos arbitrarios, ^{[ 4 ]} pero resoluble 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${\displaystyle n}$Los puntos en posición general (no tres en una línea) en dos o más dimensiones tienen al menos un número logarítmico de puntos en posición convexa. ^{[ 6 ]} Si${\displaystyle n}$Se eligen puntos uniformemente al azar en un cuadrado unitario , 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 pide el número máximo${\displaystyle \nu (d)}$de tal manera que cada conjunto de${\displaystyle \nu (d)}$puntos en posición general en un${\displaystyle d}$El espacio proyectivo de dimensión tiene una transformación proyectiva a un conjunto en posición convexa. Los límites conocidos son:${\displaystyle 2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil }$. ^{[ 8 ]}