Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1· openaiHugging Face Frontier Reasoning Traces

Write an algorithm to compute the convex hull of a set of points.

  1. User

    Write an algorithm to compute the convex hull of a set of points.

  2. Assistant

    Developing a convex hull algorithm

    The user is looking for an algorithm to compute the convex hull of a set of points, likely in computational geometry. I should consider multiple algorithms, such as Graham scan, Jarvis march, Andrew's monotone chain, and QuickHull. They haven't specified the language or dimensionality, so I’ll assume 2D planar points. I think I’ll focus on Andrew's monotone chain algorithm since it's efficient and robust. I’ll provide pseudocode, an explanation of the cross product and sorting, along with the essential steps. Here is a standard O(n log n) algorithm to compute the convex hull of a finite set of 2D points: Andrew’s monotone chain algorithm.

    It returns the hull as a list of vertices in counter-clockwise (CCW) order.


    Idea

    1. Sort points by x, then by y.
    2. Build the lower hull from left to right.
    3. Build the upper hull from right to left.
    4. Concatenate lower and upper (excluding the last point of each to avoid duplication).

    The key geometric test is the cross product to detect whether three consecutive points make a left turn, right turn, or are collinear.


    Geometry helper

    For three points O, A, B, define:

    cross(O, A, B) = (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)
    
    • cross > 0 → O→A→B makes a counter-clockwise (left) turn
    • cross < 0 → clockwise (right) turn
    • cross = 0 → points are collinear

    For the convex hull, we remove points that would make a right turn (non-convex corner).


    Pseudocode

    Assume points are given as an array P[0..n-1], each P[i] has fields .x and .y.

    function convex_hull(P):
        n = length(P)
        if n <= 1:
            return copy(P)
    
        // 1. Sort by x, then y
        sort P by (x ascending, then y ascending)
    
        // 2. Build lower hull
        lower = empty list
        for each point p in P:
            while length(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
                pop last element from lower
            append p to lower
    
        // 3. Build upper hull
        upper = empty list
        for each point p in P in reverse order:
            while length(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
                pop last element from upper
            append p to upper
    
        // 4. Concatenate lower and upper to get full hull
        // Last point of each list is same as first point of the other list
        pop last element from lower
        pop last element from upper
        hull = concatenate(lower, upper)
    
        return hull
    
    
    function cross(O, A, B):
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)
    

    Notes

    • Complexity: O(n log n) due to sorting; the hull construction itself is O(n).
    • The result hull is a list of vertices in CCW order forming the convex polygon.
    • To keep collinear boundary points, change the condition < = 0 to < 0 in the while loops.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.