Diferencia entre revisiones de «Envolvente convexa»

Contenido eliminado Contenido añadido
NachoGD (discusión · contribs.)
Muro Bot (discusión · contribs.)
m Bot: Arreglando espacios en los enlaces; cambios cosméticos
Línea 1:
[[Archivo:Envoltura_convexa_de_puntosEnvoltura convexa de puntos.png||right|280px|thumb|Envoltura convexa de un conjunto de 15 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>
 
Línea 18:
=== Algoritmos para el cálculo de la envoltura 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>'').
 
* '''[[Método de Graham|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'').
 
* '''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.
 
== Referencias ==
<references />
 
[[Categoría:Álgebra lineal]]