The Convex Hull category's ninth entry, and a third kind of "different question" alongside
Rotating Calipers and
Convex Hull Trick: every other entry in this
category takes an unordered set of points and has to work for its
O(n log n) — sorting by angle, sorting by coordinate, or accepting a worse bound in
exchange for skipping the sort. Melkman's Algorithm assumes something extra: the points aren't an
unordered set at all, they're the vertices of a simple polygon, already listed in
boundary order (clockwise or counterclockwise, either works). That one assumption is enough to drop
the sort entirely and compute the convex hull in genuine O(n) — a single left-to-right
pass with a double-ended queue, each vertex tested against only the two edges currently at the
deque's own ends.
Ten vertices tracing a five-pointed star, in boundary order: an outer tip, an inner notch, an outer tip, an inner notch, and so on around. Five of the ten (the outer tips) are on the convex hull; the five inner notches are not. Press Step or Run to watch the deque grow — each vertex is either found already inside the current hull-so-far and skipped in one comparison, or pushed onto both ends of the deque, first popping off any earlier vertices the new one now makes redundant. The checkbox feeds the identical ten points in a shuffled order instead of the polygon's own boundary order — same set of points, same algorithm, no sort added back in — see Pitfalls for what that does to the answer.
The deque D always holds the convex hull of every vertex processed so far, in
counterclockwise order, with the same point sitting at both the bottom and the top — a closed loop
written out flat. Seed it from the first three non-collinear vertices: the algorithm checks the
turn they make and writes them into the deque already in the correct counterclockwise order,
whichever way the input itself turns. From there, each new vertex p is tested against
exactly two edges — the bottom edge (the first two entries in the deque) and the top edge (the last
two) — using the same cross(o, a, b) = (a.x−o.x)(b.y−o.y) − (a.y−o.y)(b.x−o.x) every
other Convex Hull entry on this site already uses. If p is left of both
edges, it's inside the current hull and gets skipped — no deque change, no other edge ever needs
checking.
That two-edge check is the part that only works because the vertices arrive in simple-polygon
order. In a genuinely unordered algorithm, "left of the bottom and top edge" would say nothing
about the other |D|−2 edges in between — a point could still poke outside one of
those. Melkman's own correctness proof is that it can't, given boundary-ordered input:
the untested middle of the deque is protected by the polygon's own simplicity, because a boundary
that doesn't cross itself can't have already-confirmed hull edges quietly violated by a vertex that
hasn't been reached yet. When p does fail the check, the fix is symmetric on both
ends: pop vertices off the bottom while the bottom edge would make a clockwise (or straight) turn
through p, then push p onto the bottom; do the same at the top. Every
vertex is pushed onto the deque at most twice (once per end) and popped at most as many times as it
was pushed, so the total work across all n vertices is O(n) — no
per-comparison cost ever depends on how big the deque has gotten, unlike a sort's
O(log n) per comparison.
function melkmanHull(polygon) {
// polygon: vertices of a simple polygon, in boundary order (cw or ccw)
function cross(o, a, b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
let i = 0;
while (i + 2 < polygon.length && cross(polygon[i], polygon[i + 1], polygon[i + 2]) === 0) i++;
const [p0, p1, p2] = [polygon[i], polygon[i + 1], polygon[i + 2]];
// seed the deque with the first triangle, already written counterclockwise
let D = cross(p0, p1, p2) > 0 ? [p2, p0, p1, p2] : [p2, p1, p0, p2];
for (let k = i + 3; k < polygon.length; k++) {
const p = polygon[k];
// inside the current hull already? left of both extreme edges — skip in O(1)
if (cross(D[0], D[1], p) > 0 && cross(D[D.length - 2], D[D.length - 1], p) > 0) continue;
while (D.length >= 2 && cross(D[0], D[1], p) <= 0) D.shift();
D.unshift(p);
while (D.length >= 2 && cross(D[D.length - 2], D[D.length - 1], p) <= 0) D.pop();
D.push(p);
}
return D; // first and last entries are the same point — a closed ccw loop
}Feed the same points in any order other than the polygon's own boundary order, and the
two-edge check silently stops proving what it claims to prove. Checked directly, not just
argued: the demo's own ten star points, fed in one specific shuffled order, produce a 4-vertex
result that's missing a real hull vertex outright — not a different valid hull, an
incomplete one, confirmed by comparing against an independent brute-force hull of the same
ten points. The failure isn't cosmetic or rare: an O(n) stress harness generating
20,000 genuinely simple random polygons and running this exact algorithm against a brute-force hull
on each found zero mismatches, but a separate check that instead scrambled each polygon's own
vertex order before running the identical code found the wrong-hull failure reproduces on
essentially every scrambled trial that wasn't already accidentally close to boundary order. The
two-edge check has no way to notice its assumption was violated — it just returns a confidently
wrong, smaller-than-correct hull with no error, which is a sharper failure than the collinear-point
or tiebreak pitfalls documented on this site's other Convex Hull entries. This is also why
Melkman's Algorithm can't simply replace Graham Scan or
Quickhull for the general "hull of an arbitrary point
set" question — it answers a different, narrower question that happens to be answerable faster.
The deque needs real push/pop at both ends, not a fixed-size array with two moving
index variables. An early version of this page's own verification script tried exactly
that shortcut — decrementing a bot index to "make room" at the front of a plain
array — and crashed immediately reading past index 0 the first time two vertices needed popping
from the bottom in the same step. The fix was using real deque operations
(shift/unshift/pop/push), not a larger
correctness bug, but it's a reminder that "amortized O(n) pushes and pops" only holds if pushing
and popping are actually O(1) at both ends, which a plain JavaScript array only gives at one end
without care.
Time: O(n) — genuinely no sort, unlike every other from-scratch
Convex Hull entry on this site. The amortized argument is the same shape as a monotonic stack's:
each of the n vertices is pushed onto the deque at most twice (bottom and top) across
the whole run, and every pop removes a vertex that was pushed earlier, so total pops can't exceed
total pushes. Space: O(h) for the deque itself, where
h is the final hull size — the same output-sensitive footprint as
Jarvis March, reached by a completely different route
(pruning a deque instead of wrapping outward one confirmed vertex at a time). The catch is entirely
in the input requirement, not the cost: Graham Scan,
Jarvis March,
Quickhull,
Monotone Chain,
Divide-and-Conquer Convex Hull, and
Chan's Algorithm all work on any point set handed to
them in any order, because they each spend real work (a sort, or a wrap, or a recursive split)
establishing structure the input doesn't already have. Melkman's Algorithm is only ever the right
tool when that structure already exists for free — a simple polygon's boundary walk, a GPS track, a
scanned outline — never for a bag of points with no known order. See
Choosing a Convex Hull Algorithm for
where this fits alongside the other eight.