Convex hull properties and algorithms (Q984371)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Convex hull properties and algorithms |
scientific article |
Statements
Convex hull properties and algorithms (English)
0 references
19 July 2010
0 references
The convex hull (CH) is a central problem for a variety of applications of computational geometry. The authors investigate CH properties and derive some new properties about vertices and edge slopes. These properties are used to provide a CH algorithm for a planar point set and another algorithm for two available CHs. The former of these runs faster than the algorithm of \textit{H. Brönnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison} and \textit{G. Toussaint} [Theor. Comput. Sci. 321, No.~1, 25--40 (2004; Zbl 1068.68153)]. The other algorithm is better than conventional methods. It is also observed that the theoretical analysis and experimental results show that the algorithms proposed by the authors are practical and efficient.
0 references
Convex hull
0 references
extreme points
0 references
point set
0 references
computational geometry
0 references
algorithms
0 references