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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    Convex hull
    0 references
    extreme points
    0 references
    point set
    0 references
    computational geometry
    0 references
    algorithms
    0 references

    Identifiers