Diferencia entre revisiones de «Envolvente convexa»
Contenido eliminado Contenido añadido
m Bot: Arreglando espacios en los enlaces; cambios cosméticos |
|||
Línea 1:
[[Archivo:
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]]
|