What is the Convex Hull problem, and how can it be solved?

Instruction: Explain the planar convex-hull problem and an algorithm to solve it. State how duplicates, empty input and collinear points are handled, and discuss complexity and numerical assumptions.

Context: This question tests the candidate's knowledge of the Convex Hull problem, a fundamental problem in computational geometry, and the algorithms used to solve it.

Updated

Official answer

For planar points, the convex hull is their smallest containing convex set. It may be empty, a point or a line segment rather than a polygon. The following monotone-chain implementation returns distinct extreme vertices in counterclockwise order, excluding intermediate collinear boundary points:

def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 1:
        return points

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

    def half(sequence):
        result = []
        for p in sequence:
            while len(result) >= 2 and cross(result[-2], result[-1], p) <= 0:
                result.pop()
            result.append(p)
        return result

    return half(points)[:-1] + half(reversed(points))[:-1]

Sorting costs O(n log n); each point is pushed and popped only a bounded number of times during scanning, for O(n) additional work and space. All-collinear input returns its two endpoints.

The example is suitable for finite integer coordinates with Python's exact integer arithmetic. Operation costs grow with integer size. Floating-point near-collinearity needs a deliberate robust-predicate policy; NaN and infinity are outside this contract. The complexity bound alone does not prove a real-time deadline.

Related Questions