Convex hull of a simple polygon

It can be computed in linear time, faster than algorithms for convex hulls of point sets.

[2] Finding the convex hull of a simple polygon can be performed in linear time.

Several early publications on this problem were discovered to be incorrect, often because they led to intermediate states with crossings that caused them to break.

Like the Graham scan algorithm for convex hulls of point sets, it is based on a stack data structure.

The algorithm traverses the polygon in clockwise order, starting from a vertex known to be on the convex hull (for instance, its leftmost point).

[5] A similar method can also be used to construct convex hulls of piecewise smooth closed curves in the plane.

According to the Erdős–Nagy theorem, this flipping process eventually terminates, by reaching a convex polygon.

The convex hull of a simple polygon (blue). Its four pockets are shown in yellow; the whole region shaded in either color is the convex hull.