Andrew's Monotone Chain Convex Hull

The Algorithm

A. M. Andrew's 1979 variant of Graham scan replaces the polar-angle sort with a plain coordinate sort, at the cost of scanning twice instead of once:

Sort all points by $(x, y)$ — a numeric sort, no trigonometry, no choice of pivot.
Build the lower hull: scan left to right, maintaining a stack with the same left-turn rule as Graham scan.
Build the upper hull: scan right to left (or equivalently, reverse the sorted list), maintaining a fresh stack with the same rule.
Concatenate the lower and upper hulls (dropping the duplicated first/ last points where they meet) to get the full hull in order.

def orientation(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def half_hull(points):
    hull = []
    for p in points:
        while len(hull) >= 2 and orientation(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull


def monotone_chain(points):
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    lower = half_hull(pts)
    upper = half_hull(pts[::-1])
    return lower[:-1] + upper[:-1]  # drop each half's duplicated endpoint


pts = [(0, 0), (4, 0), (4, 4), (0, 4), (2, 2), (2, -1)]
print(monotone_chain(pts))

#include <algorithm>
#include <vector>

struct Point {
    double x, y;
    bool operator<(const Point& o) const { return x != o.x ? x < o.x : y < o.y; }
};

double orientation(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

std::vector<Point> halfHull(const std::vector<Point>& points) {
    std::vector<Point> hull;
    for (const auto& p : points) {
        while (hull.size() >= 2 &&
               orientation(hull[hull.size() - 2], hull.back(), p) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }
    return hull;
}

std::vector<Point> monotoneChain(std::vector<Point> points) {
    std::sort(points.begin(), points.end());
    points.erase(std::unique(points.begin(), points.end(),
        [](const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }), points.end());
    if (points.size() <= 2) return points;

    auto lower = halfHull(points);
    std::reverse(points.begin(), points.end());
    auto upper = halfHull(points);

    lower.pop_back();
    upper.pop_back();
    lower.insert(lower.end(), upper.begin(), upper.end());
    return lower;
}

Core Insight: the "drop the duplicated endpoint" step is not an edge case to special-case away — the lower hull's last point is the upper hull's first point (the rightmost point of the set) by construction, and symmetrically for the leftmost point. Concatenating without dropping would silently duplicate two vertices in the output.

Why Prefer This Over Graham Scan

Both algorithms are $O(n \log n)$ and share the identical stack invariant, so the choice is mostly about implementation ergonomics: monotone chain avoids the pivot-selection special case and the angle-comparator function entirely, at the cost of running the scan twice. In practice this makes monotone chain the more common choice in competitive programming and production libraries, precisely because a plain sort() call is harder to get wrong than a custom polar-angle comparator.

Worked Example

Trace It Yourself

Run monotone_chain on [(0,0), (4,0), (4,4), (0,4), (2,2), (2,-1)] — the same input used in the Graham scan trace. Confirm both algorithms agree on the same 5-vertex hull, in possibly different starting order but the same cyclic sequence.

Cookie Consent

Andrew's Monotone Chain Convex Hull

The Algorithm

Why Prefer This Over Graham Scan

Trace It Yourself

Related Reading

Convex Hulls in the Plane

Graham Scan