文章基本信息

标题：Nuevo Algoritmo para la Construcción de la Envolvente Convexa en el Plano
其他标题：New Algorithm to Construct a Planar Convex Hull
本地全文：下载
作者：Buitrago, Oscar Y ; Ramírez, Andrés L ; Britto, Rodrigo A 等
期刊名称：Información tecnológica
印刷版ISSN：0716-8756
电子版ISSN：0718-0764
出版年度：2015
卷号：26
期号：4
页码：137-144
DOI：10.4067/S0718-07642015000400017
出版社：Centro de Información Tecnológica
摘要：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.
其他摘要：In this paper we present a new algorithm for finding the convex hull C(P) for P sets of n points in R². This problem has been widely studied in computational geometry and has important applications in engineering and other fields of knowledge. The proposed algorithm is based on a directional search of supporting hyperplanes and a variant which includes separating hyperplanes to reduce the number of evaluated points, ignoring the interior ones. The application of the proposed algorithm is illustrated using an example. The complexity of the algorithm obtained is O(máx (nv o; nvº)), v o≤ v ≤ n y vº≤ v ≤ n, where v is the number of vertices of the convex hull.
关键词：algoritmo;envolvente convexa;hiperplano soporte;búsqueda direccional
其他关键词：algorithm;convex hull;supporting hyperplane;directional search