Convex Hull

The convex hull of a set of points in a plane is the smallest convex polygon that contains all the points. Imagine stretching a rubber band around a set of nails hammered into a board; the shape the rubber band takes is the convex hull. This is a fundamental problem in computational geometry with numerous applications, from collision detection in video games to pattern recognition in image analysis. There are several algorithms to compute the convex hull. The Graham scan algorithm is a classic method. It first finds the point with the lowest y-coordinate (the 'anchor') and then sorts all other points by the polar angle they make with the anchor. It then processes these points in order, maintaining a stack of vertices of the current hull. For each point, it checks if adding it maintains a 'left turn'. If it creates a 'right turn', it means the previous point on the stack is not part of the hull, so it's popped off. This continues until a left turn is made. Another popular algorithm is the Monotone Chain (or Andrew's algorithm), which builds the upper and lower hulls of the point set separately. Both algorithms have a time complexity of O(n log n), dominated by the initial sorting step.