a convex-hull algorithm
Hammer nails at a set of points and stretch a rubber band around them all: when it snaps tight, it traces the smallest convex shape containing every point. That outline is the convex hull, and a convex-hull algorithm is a procedure that computes it — finds exactly which points are corners and in what order they go around the boundary. It is the most basic nontrivial problem in computational geometry, and the gateway to Voronoi, Delaunay, and linear programming.
The convex hull of a finite point set P is the smallest convex set containing P, equivalently the set of all convex combinations of points of P; in the plane its boundary is a convex polygon whose vertices are a subset of P. Several algorithms compute it. Graham's scan sorts the points by angle around the lowest point, then walks the sorted list pushing points onto a stack and popping any that would create a right (clockwise) turn, running in O(n log n) dominated by the sort. Andrew's monotone-chain variant sorts by x-coordinate and builds upper and lower hulls. Gift wrapping (Jarvis march) repeatedly finds the next hull edge by picking the most counterclockwise point, costing O(n*h) where h is the number of hull vertices — fast when the hull is small. Quickhull mimics quicksort, recursively discarding interior points, with good average behavior. The key primitive throughout is the orientation test: the sign of a 2x2 (or 3x3) determinant telling whether three points turn left, right, or are collinear.
Convex-hull algorithms matter as a building block: the planar O(n log n) bound is optimal (sorting reduces to convex hull), and in higher dimensions the hull underlies Delaunay triangulation (lift to a paraboloid, take the lower hull), linear-programming feasibility, and collision detection. Honest caveats: the output size matters — in d dimensions the hull of n points can have on the order of n^{floor(d/2)} faces, so 'compute the convex hull' is cheap in 2D/3D but can explode combinatorially in high dimensions; and these algorithms are notoriously sensitive to floating-point error in the orientation test, where a near-collinear triple can be misjudged and corrupt the hull, so robust implementations use exact or adaptive-precision arithmetic and explicit handling of collinear and duplicate points.
Graham scan on a set of planar points: pick the lowest point as anchor, sort the rest by polar angle around it, then sweep the sorted list maintaining a stack — for each new point, while the last two stack points plus the new one make a clockwise turn (orientation determinant negative), pop the stack; otherwise push. When the sweep finishes the stack holds the hull vertices in counterclockwise order, all in O(n log n).
Graham scan: sort by angle, then pop every clockwise turn — what survives on the stack is the hull.
The orientation (determinant-sign) test is the algorithm's Achilles' heel: floating-point round-off on near-collinear triples can give the wrong turn direction and produce a non-convex or self-intersecting 'hull'. Robust code uses exact or adaptive-precision predicates and handles collinear and duplicate points explicitly; in high dimensions remember the output itself can be exponentially large.