Diferencia entre revisiones de «Envolvente convexa»

Contenido eliminado Contenido añadido

En renglón

Revisión actual - 17:18 13 ene 2023

Envoltura convexa de un conjunto de 8 puntos en el plano.

En matemáticas se define la envolvente convexa, envoltura convexa o cápsula convexa de un conjunto de puntos X de dimensión n como la intersección de todos los conjuntos convexos que contienen a X.^[1]

Dados k puntos $x_{1},\,x_{2},\,...,x_{k}$ su envolvente convexa C viene dada por la expresión:

$C(X)=\left\{\sum _{i=1}^{k}\alpha _{i}x_{i}\ {\Bigg |}\ x_{i}\in X,\,\alpha _{i}\in \mathbb {R} ,\,\alpha _{i}\geq 0\,,\sum _{i=1}^{k}\alpha _{i}=1\right\}$

En el caso particular de puntos en un plano, si no todos los puntos están alineados, entonces su envolvente convexa corresponde a un polígono convexo cuyos vértices son algunos de los puntos del conjunto inicial de puntos.

Una forma intuitiva de ver la envolvente convexa de un conjunto de puntos en el plano, es imaginar una banda elástica estirada que los encierra a todos. Cuando se libere la banda elástica tomará la forma de la envolvente convexa.

Alternativamente

La unión de todas las combinaciones convexas de conjuntos finitos de puntos de $A\subset R^{n}$ se denomina cápsula convexa de $A$ .^[2]

Teorema de Carathéodory

La cápsula convexa de un conjunto coincide con la unión de todas las combinaciones convexas posibles de subconjuntos finitos del conjunto $A\subset R^{n}$ que tienen a lo más $n+1$ puntos.^[2]

Cálculo de la envolvente convexa

En geometría computacional existen numerosos algoritmos para calcular la envolvente convexa de un conjunto finito de puntos, con diversos grados de complejidad computacional. La complejidad del algoritmo de resolución se suele estimar en función del número n de puntos de entrada, y el número h de puntos de la correspondiente envolvente convexa.

Algoritmos para el cálculo de la envolvente convexa en el plano

Jarvis march o gift wrapping algorithm: Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una complejidad computacional O(nh). En el peor de los casos su complejidad será O(n²).
Método de Graham: Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(n log n). Si los puntos se encuentran pre-ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(n).
Quickhull: Un método recursivo creado de forma independiente en 1977 por W. Eddy y A. Bykat. Tiene una complejidad esperada O(n log n), pero que puede degenerar a O(n^2) en el peor caso.
Divide y vencerás (Divide and conquer): Otro algoritmo de complejidad O(n log n) publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.^[3]

Referencias

↑ Weisstein, Eric W. «envolvente convexa». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
↑ ^a ^b Boss, V. (2011). Álgebra lineal. Moscú: Editorial URSS. ISBN 978-5-396-00066-7.
↑ Preparata, Franco P.; Hong, S.J. (1977). «Convex hulls of finite sets of points in two and three dimensions». Communications of the ACM 20 (2). doi:10.1145/359423.359430.

Véase también

Convexidad

Datos: Q1138624

[1] Weisstein, Eric W. «envolvente convexa». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.

[Boss-2] Boss, V. (2011). Álgebra lineal. Moscú: Editorial URSS. ISBN 978-5-396-00066-7.

[Preparata-3] Preparata, Franco P.; Hong, S.J. (1977). «Convex hulls of finite sets of points in two and three dimensions». Communications of the ACM 20 (2). doi:10.1145/359423.359430.

[1]

[2]

[3]

@@ Línea 1: / Línea 1: @@
-[[Imagen:Envoltura_convexa_de_puntos.png||right|280px|thumb|Envoltura convexa de un conjunto de 15 puntos en el plano]]
+[[File:ConvexClosure.svg|right|thumb|Envoltura convexa de un conjunto de 8 puntos en el plano.]]
-En [[matemática]] se define la '''envoltura convexa''' de un conjunto de puntos '''''X''''' de [[dimensión]] '''''n''''' como la intersección de todos los [[Convexidad|conjuntos convexos]] que contienen a '''''X'''''.<ref>[http://mathworld.wolfram.com/ConvexHull.html Mathworld]</ref>
+En [[matemáticas]] se define la '''envolvente convexa''', '''envoltura convexa '''o''' cápsula convexa''' de un conjunto de puntos '''''X''''' de [[dimensión]] '''''n''''' como la intersección de todos los [[Convexidad|conjuntos convexos]] que contienen a '''''X'''''.<ref>{{MathWorld |id=ConvexHull |title=envolvente convexa}}</ref>
-Dados k puntos <math>x_1,\, x_2,\, ...,x_k</math> su envoltura convexa ''C'' viene dada por la expresión:
+Dados k puntos <math>x_1,\, x_2,\, ...,x_k</math> su envolvente convexa ''C'' viene dada por la expresión:<br>
+<br><math>
+C(X) =\left\{\sum_{i=1}^k \alpha_i x_i \ \Bigg | \ x_i\in X, \, \alpha_i\in \mathbb{R}, \, \alpha_i \geq 0 \, , \sum_{i=1}^k \alpha_i=1\right\}
+</math><br>
+<br>
+En el caso particular de puntos en un plano, si no todos los puntos están alineados, entonces su envolvente convexa corresponde a un [[polígono convexo]] cuyos vértices son algunos de los puntos del conjunto inicial de puntos.
+Una forma intuitiva de ver la envolvente convexa de un conjunto de puntos en el plano, es imaginar una banda elástica estirada que los encierra a todos. Cuando se libere la banda elástica tomará la forma de la envolvente convexa.
-<math>
-C(X) =\left\{\sum_{i=1}^k \alpha_i x_i \ \Bigg |  \ x_i\in X, \, \alpha_i\in \mathbb{R}, \, \alpha_i \geq 0 \, , \sum_{i=1}^k \alpha_i=1\right\}.
-</math>
+==Alternativamente==
-En el caso particular de puntos en un plano, si no todos los puntos están alineados, entonces su envoltura convexa corresponde a un polígono convexo cuyos vértices son algunos de los puntos del conjunto inicial de puntos.
+La unión de todas las combinaciones convexas de [[Conjunto finito|conjuntos finitos]] de puntos de <math> A \subset R^n</math> se denomina ''cápsula convexa'' de <math>A</math>.<ref name="Boss">{{cita libro|apellidos1=Boss|nombre1=V.|título=Álgebra lineal|fecha=2011|editorial=Editorial URSS|ubicación=Moscú|isbn=978-5-396-00066-7}}</ref>
+===Teorema de Carathéodory===
-Una forma intuitiva de ver la envoltura convexa de un conjunto de puntos en el plano, es imaginar una banda elástica estirada que los encierra a todos. Cuando se libere la banda elástica tomará la forma de la envoltura convexa.
+La cápsula convexa de un conjunto coincide con la unión de todas las combinaciones convexas posibles de subconjuntos finitos del conjunto <math>A \subset R^n</math> que tienen a lo más <math> n + 1</math> puntos.<ref name="Boss" />
-==Cálculo de la envoltura convexa==
+== Cálculo de la envolvente convexa ==
-En geometría computacional existen numerosos algoritmos para calcular la envoltura convexa de un conjunto finito de puntos, con diversos grados de [[complejidad computacional]].
-La complejidad del algoritmo de resolución se suele estimar en función de el número '''''n''''' de puntos de entrada, y el número '''''h''''' de puntos de la correspondiente envoltura convexa.
+En [[geometría computacional]] existen numerosos algoritmos para calcular la envolvente convexa de un conjunto finito de puntos, con diversos grados de [[complejidad computacional]].
-===Algoritmos para el cálculo de la envoltura convexa en el plano===
+La complejidad del algoritmo de resolución se suele estimar en función del número '''''n''''' de puntos de entrada, y el número '''''h''''' de puntos de la correspondiente envolvente convexa.
+=== Algoritmos para el cálculo de la envolvente convexa en el plano ===
-*'''Jarvis march''' o ''gift wrapping algorithm''. Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una [[complejidad computacional]] O(''nh''). En el peor de los casos su complejidad será O(''n<sup>2</sup>'').
+* '''Jarvis march''' o ''gift wrapping algorithm'': Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una [[complejidad computacional]] O(''nh''). En el peor de los casos su complejidad será O(''n<sup>2</sup>'').
-*'''Graham scan'''. Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(''n'' log ''n''). Si los puntos se encuentran ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(''n'').
+* '''[[Método de Graham]]''': Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(''n'' log ''n''). Si los puntos se encuentran pre-ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(''n'').
+* '''[[Quickhull]]''': Un método recursivo creado de forma independiente en 1977 por W. Eddy y A. Bykat. Tiene una complejidad esperada O(n log n), pero que puede degenerar a O(n^2) en el peor caso.
-*'''Divide and conquer'''. Otro algoritmo de complejidad O(''n'' log ''n'') publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.
+* '''Divide y vencerás''' (''Divide and conquer''): Otro algoritmo de complejidad O(''n'' log ''n'') publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.<ref name=Preparata>{{Cita publicación|apellidos=Preparata |nombre=Franco P.|author-link=Franco P. Preparata|apellidos2=Hong|nombre2=S.J. |título=Convex hulls of finite sets of points in two and three dimensions |publicación=[[Communications of the ACM]] |volumen=20 |número=2 |año=1977 |doi=10.1145/359423.359430 |issn= |url= }}</ref>
-==Referencias==
-<references/>
-{{esbozo|matemática}}
+== Referencias ==
+{{listaref}}
+==Véase también ==
+[[Convexidad]]
+{{Control de autoridades}}
 [[Categoría:Álgebra lineal]]
+[[Categoría:Geometría convexa]]
+[[Categoría:Algoritmos geométricos]]
-[[de:Konvexe Hülle]]
+[[Categoría:Procesamiento en geometría]]
-[[en:Convex Hull]]
+[[Categoría:Geometría computacional]]
-[[eo:Konveksa koverto]]
+[[Categoría:Operadores de cierre]]
-[[fr:Enveloppe convexe]]
-[[it:Inviluppo convesso]]
-[[he:קמור]]
-[[pl:Otoczka wypukła]]
-[[pt:Envoltória convexa]]
-[[ru:Выпуклая оболочка]]
-[[sl:Konveksna ogrinjača]]
-[[sv:Konvext område]]
-[[vi:Bao lồi]]
-[[zh:凸包]]