Convex hull properties and algorithms (Q984371)

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.