Title
New algorithm to construct a planar convex hull
DOI
https://doi.org/10.4067/S0718-07642015000400017
Document Type
Article
Publication Date
1-1-2015
Publication Title
Informacion Tecnologica
Abstract
In this paper we present a new algorithm for finding the convex hull C(P) for P sets of n points in R2. 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(max (nvo; nvo)), vo ≤ v ≤ n y vo ≤ v ≤ n, where v is the number of vertices of the convex hull.
Volume
26
Issue
4
First Page
137
Last Page
144
ISSN
07168756
Recommended Citation
Buitrago, Oscar Y.; Ramírez, Andrés L.; and Britto, Rodrigo A., "New algorithm to construct a planar convex hull" (2015). Scopus Unisalle. 451.
https://ciencia.lasalle.edu.co/scopus_unisalle/451
Identifier
SCOPUS_ID:84940372820