Convex hull, sweep lines and robust geometry

A convex hull is the smallest convex polygon enclosing the points, not a circle. Andrew’s monotone chain sorts points then builds lower and upper chains. A cross product measures orientation; remove the last point when it creates the wrong turn. Each point is pushed and popped at most once, so chain construction is linear. Graham scan uses angular ordering; Jarvis march takes O(nh) for h output vertices.

A wrong sign can change geometric topology. Arbitrary floating-point epsilon is not universally reliable. Avoid integer overflow and use robust orientation predicates or appropriate exact arithmetic for floating inputs. Specify duplicates, collinear input and whether boundary-collinear points should be retained.

Sweep-line methods process ordered events and maintain an active set. Equal-coordinate event ordering and consistent comparisons matter. Voronoi diagrams and Delaunay triangulations model proximity; hulls do not solve every geometric problem. Squared-distance comparison avoids square roots, but not overflow.

def 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 chain(ps):
        out=[]
        for p in ps:
            while len(out)>1 and cross(out[-2],out[-1],p)<=0: out.pop()
            out.append(p)
        return out
    return chain(points)[:-1]+chain(points[::-1])[:-1]
assert len(hull([(0,0),(1,0),(1,1),(0,1),(.5,.5)]))==4