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.[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]
Propiedades
editarLa 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 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 se eligen uniformemente al azar en un cuadrado unidad, la probabilidad de que estén en posición convexa es[7]
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 . [8]
Referencias
editar- ↑ a b Matoušek, Jiří (2002), Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer-Verlag, p. 30, ISBN 978-0-387-95373-1.
- ↑ Tóth, Géza; Valtr, Pavel (2005), «The Erdős-Szekeres theorem: upper bounds and related results», Combinatorial and computational geometry, Math. Sci. Res. Inst. Publ. 52, Cambridge: Cambridge Univ. Press, pp. 557-568, MR 2178339.
- ↑ Deĭneko, Vladimir G.; Hoffmann, Michael; Okamoto, Yoshio; Woeginger, Gerhard J. (2006), «The traveling salesman problem with few inner points», Operations Research Letters 34 (1): 106-110, MR 2186082, doi:10.1016/j.orl.2005.01.002.
- ↑ Mulzer, Wolfgang; Rote, Günter (2008), «Minimum-weight triangulation is NP-hard», Journal of the ACM 55 (2), Article A11, arXiv:cs.CG/0601002, doi:10.1145/1346330.1346336.
- ↑ Klincsek, G. T. (1980), «Minimal triangulations of polygonal domains», Annals of Discrete Mathematics 9: 121-123, doi:10.1016/s0167-5060(08)70044-x.
- ↑ Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463-470.
- ↑ Valtr, P. (1995), «Probability that n random points are in convex position», Discrete and Computational Geometry 13 (3-4): 637-643, MR 1318803, doi:10.1007/BF02574070.
- ↑ Forge, David; Las Vergnas, Michel; Schuchert, Peter (2001), «10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope», Combinatorial geometries (Luminy, 1999), European Journal of Combinatorics 22 (5): 705-708, MR 1845494, doi:10.1006/eujc.2000.0490.
Datos: Q17007762
