Erect the Fence

Erect the Fence asks for the convex hull: given a set of trees (points), find the ones that lie on the smallest fence (convex polygon) that encloses every tree. It is the classic gateway to computational geometry, and the cleanest way to solve it is Andrew monotone chain.

The slow way first

The brute-force convex-hull test is the gift-wrapping idea: for every pair of points, check whether all the other points lie on one side of the line through them. If they do, that pair is a hull edge. That works but it is O(n³) — three nested considerations (two endpoints plus a scan of everyone else).

The question to ask: can I avoid re-checking every pair? If I first sort the points left to right, I can walk through them once and grow the boundary incrementally, only ever undoing a recent bad choice. That is what monotone chain does, in O(n log n) — dominated by the sort.

The idea: sort, then sweep, popping right turns

Sort the points by x (ties by y). Then build the hull in two sweeps:

• First chain — sweep left to right, keeping a stack. Before pushing a new point, look at the last two points already on the stack. If the turn they make with the new point is a right (clockwise) turn, the middle point is inside the boundary, so pop it. Repeat until the turn is a left turn, then push.
• Second chain — do the exact same sweep right to left.

Concatenate the two chains and you have the whole fence. The turn direction is measured with the cross product of the two edge vectors.

The cross product cross(o, a, b) = (a.x − o.x)(b.y − o.y) − (a.y − o.y)(b.x − o.x) is positive for one turn direction, negative for the other, and exactly zero when the three points are collinear. Using a strict < 0 for the pop keeps collinear points on the fence — which is exactly what this problem wants.

Walk through it

Step through the animation. The trees are sorted, then the first sweep grows the top edge: every time a new tree makes a right turn, the middle tree dims out and its edge is removed. The second sweep does the same for the bottom edge. The cross-product sign under the canvas drives every pop. The two interior trees end up dimmed; the five corner trees form the fence.

Pseudocode

sort points by (x, then y)
 
build the first chain (left to right):
    for each point p:
        while the chain has >= 2 points and cross(second-last, last, p) < 0:
            pop the last point          # it made a right turn -> inside
        push p
 
build the second chain (right to left), the same way
 
the hull is the union of the two chains

The Python solution

def outer_trees(points):
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
 
    points = sorted(map(tuple, points))
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:
            lower.pop()
        lower.append(p)
 
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
            upper.pop()
        upper.append(p)
 
    return list({tuple(p) for p in lower + upper})

• cross(o, a, b) returns the signed area of the turn o → a → b; its sign tells you left vs right.
• sorted(map(tuple, points)) puts the trees in (x, then y) order and makes them hashable for the final dedupe.
• The lower loop builds the first chain. The while pops any point that makes a right turn (cross < 0), because that point is interior to the boundary being traced.
• The upper loop repeats the sweep over the points in reverse, tracing the opposite edge.
• lower + upper double-counts the two shared corners (the leftmost and rightmost trees), so we drop duplicates with a set. Using < 0 (strict) means collinear boundary trees survive both sweeps and stay in the answer.

Complexity

Each point is pushed once and popped at most once across a sweep, so the two sweeps are O(n) total. The sort is the bottleneck at O(n log n). The hull stacks use O(n) extra space.

When this pattern shows up

Practice