Nuevo Algoritmo para la Construcción de la Envolvente Convexa en el Plano
En el presente trabajo se presenta una nuevo algoritmo para encontrar la envolvente convexa C(P) para un conjuntos P de n puntos en R². Este problema ha sido ampliamente estudiado en la geometría computacional ya que tiene importante aplicaciones en la ingeniera y otros campos del conocimiento. El a...
Guardado en:
Autores principales: | , , |
---|---|
Lenguaje: | Spanish / Castilian |
Publicado: |
Centro de Información Tecnológica
2015
|
Materias: | |
Acceso en línea: | http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0718-07642015000400017 |
Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
Sumario: | En el presente trabajo se presenta una nuevo algoritmo para encontrar la envolvente convexa C(P) para un conjuntos P de n puntos en R². Este problema ha sido ampliamente estudiado en la geometría computacional ya que tiene importante aplicaciones en la ingeniera y otros campos del conocimiento. El algoritmo propuesto se basada en búsquedas direccionales de hiperplanos soporte y una variante que incorpora hiperplanos separadores que permiten reducir el número de puntos evaluados, descartando los que son interiores. La aplicación del algoritmo propuesto se ilustra mediante un ejemplo. La complejidad del algoritmo obtenido es O(máx (nv o; nvº)), v o≤ v ≤ n y vº≤ v ≤ n, donde v es el número de vértices de la envolvente convexa. |
---|