Melkman's Algorithm

Purpose: Compute the convex hull of a simple polyline (a path that does not self-intersect) in $O(n)$ time — online, one point at a time, with no sorting.

Why linear is possible here

A general point set needs $\Omega (n\log n)$ for its hull (sorting reduces to hull construction). But if the points arrive as a simple polyline, consecutive points are already spatially coherent, and that extra structure is exactly enough to drop the log factor.

Algorithm

Maintain the hull as a deque $D$ holding the hull vertices in order, with the same vertex at both ends (so the deque represents a closed polygon).

For each new point $v$:

1. If $v$ is inside the current hull — i.e. it makes a left turn with the front pair and with the back pair — skip it.
2. Otherwise:
   • pop from the front while the first three deque elements plus $v$ make a non-left turn;
   • pop from the back while the last three plus $v$ make a non-left turn;
   • push $v$ onto both the front and the back.

// D is a deque; points arrive in polyline order
void add(deque<Point>& D, Point v) {
    if (D.size() >= 3 &&
        cross(D[1] - D[0], v - D[0]) > 0 &&
        cross(D[D.size()-1] - D[D.size()-2], v - D[D.size()-2]) > 0)
        return;                                  // inside the hull
    while (D.size() >= 2 && cross(D[1] - D[0], v - D[0]) <= 0) D.pop_front();
    while (D.size() >= 2 &&
           cross(D[D.size()-1] - D[D.size()-2], v - D[D.size()-2]) <= 0) D.pop_back();
    D.push_front(v);
    D.push_back(v);
}

Complexity

• Time: $O(n)$ — each point is pushed at most twice and popped at most twice
• Space: $O(n)$
• Online: the hull is correct after every insertion, without reprocessing

The simplicity requirement

The polyline must not self-intersect. The proof relies on the fact that a simple path can only “wrap around” the current hull in one direction, which is what guarantees the deque never needs a pop from the middle. Feed it an arbitrary point order and it produces garbage.

When it applies

• Hull of a simple polygon — a polygon’s boundary is a simple polyline; this is the canonical use
• Hull of a path/trajectory — GPS traces, robot paths, contour following
• Incremental hull with coherent input — streaming geometry where points arrive along a curve
• Preprocessing step — hull of each part of a polygon before merging

Convex hull decision table

Input	Best algorithm	Time
Arbitrary point set	Andrew’s monotone chain	$O(n\log n)$
Arbitrary set, small hull	Chan	$O(n\log h)$
Already sorted by $x$	monotone chain, skip the sort	$O(n)$
Simple polyline / polygon	Melkman	$O(n)$
Points added and removed online	dynamic hull (balanced BST of hull edges)	$O({\log }^{2}n)$

Variants / Use Cases

• Convex Hull — the topic page
• Andrew’s monotone chain — the general-purpose default
• Rotating calipers — diameter and width, once you have the hull
• Monotonic stack — the same “pop while the turn is wrong” idea in one dimension