Diferencia entre revisiones de «Posición convexa»

Contenido eliminado Contenido añadido

En renglón

Revisión del 19:43 6 nov 2023

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 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 los puntos 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 ninguno de ellos está contenido en la envolvente convexa de los demás.^[2]

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 el casco convexo. ^[3] De manera similar, el 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 complejidad temporal mediante programación dinámica para puntos en posición convexa. ^[5]

El Teorema de Erdős-Szekeres garantiza que cada conjunto de puntos $n$ en posición general (no tres en línea) en dos o más dimensiones tenga al menos un número logarítmico de puntos en posición convexa. ^[6] Si los puntos $n$ se eligen uniformemente al azar en un cuadrado unidad, la probabilidad de que estén en posición convexa es^[7]

\left({\binom {2n-2}{n-1}}/n!\right)^{2}.

El McMullen problem solicita el número máximo $\nu (d)$ tal que cada conjunto de puntos $\nu (d)$ en posición general en un $d$ dimensional espacio proyectivo tenga un homografía (geometría) para un conjunto en posición convexa. Los límites conocidos son $2d+1\leq \nu (d)\leq 2d+\lceil (d+1)/2\rceil$ . ^[8]

Referencias

↑ ^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

[m02-1] Matoušek, Jiří (2002), Lectures on Discrete Geometry, Graduate Texts in Mathematics, Springer-Verlag, p. 30, ISBN 978-0-387-95373-1 .

[tv05-2] 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 .

[dhow06-3] 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 .

[mr08-4] 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 .

[k80-5] Klincsek, G. T. (1980), «Minimal triangulations of polygonal domains», Annals of Discrete Mathematics 9: 121-123, doi:10.1016/s0167-5060(08)70044-x .

[es35-6] Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463-470 .

[v95-7] 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 .

[flvs01-8] 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]