For *planar objects*, i.e., lying in the plane, an easy way to visualize the convex hull is to imagine a rubber band tightly stretched to encompass given objects; when released, it will assume the shape of the required convex hull.

In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexity.

Computing the convex hull means that a non-ambiguous and efficient represesentation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of ** n**, the number of input points, and

Table of contents |

2 Higher dimensions 3 Relations to other geometric structures 4 Applications |

If not all points are on the same line, then their convex hull is a convex polygon. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of halfplanes.

The convex hull of a simple polygon may be constructed in O(*n*) time.

For a finite set of points, the convex hull is a convex polyhedron. However its representation is not so simple as in the planar case. In higher dimensions, even if the vertices of a convex polyhedron are known, construction of its faces is a non-trivial task.

A number of algorithms are known for the three-dimensional case, as well as for arbitrary dimensions.

The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics. It also serves as a tool, a building block for a number of other computational-geometric algorithms.