Concepts174
Category
Meet in the Middle
Meet-in-the-middle splits a hard exponential search into two halves, enumerates each half, and then combines results efficiently.
Closest Pair of Points
The closest pair of points problem asks for the minimum Euclidean distance between any two points in the plane.
Line Sweep
Line sweep (plane sweep) is a technique that processes geometric objects by moving an imaginary line and handling events in sorted order.
Polygon Area and Centroid
The signed area of a simple polygon can be computed in O(n) using the shoelace formula, which sums cross products of consecutive vertices.
Rotating Calipers
Rotating calipers is a geometric two-pointer technique that sweeps two (or more) parallel support lines around a convex polygon.
Basic Geometry - Lines and Segments
A line can be represented by two points, a point with a direction vector, or the general form ax + by + c = 0, and these forms are interconvertible.
Convex Hull
The convex hull is the smallest convex polygon that contains all given points, like a rubber band snapped around nails on a board.
Minimum Rotation
The minimum rotation of a string is the lexicographically smallest string you can get by cutting it at some position and swapping the two parts.
Point in Polygon
Point-in-polygon decides whether a point lies outside, inside, or on the boundary of a polygon.
Orientation and CCW
Orientation (CCW test) tells whether three points make a left turn, right turn, or are collinear by using the sign of a 2D cross product.
Basic Geometry - Points and Vectors
A 2D point can be treated as a vector from the origin, so vector math (addition, scaling, dot, cross) applies directly to points.
KMP - Prefix Function Applications
The prefix function π of a string tells, for every position, the length of the longest proper prefix that is also a suffix of the prefix ending there.