Concepts318
Category
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.
Suffix Array Construction
A suffix array stores the starting indices of all suffixes of a string in lexicographic order, enabling fast substring queries and many string operations.
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.
Lyndon Factorization
A Lyndon word is a string that is strictly smaller (lexicographically) than all of its nontrivial rotations.
Broken Profile DP
Broken Profile DP is a dynamic programming technique that sweeps a grid one cell or one column at a time while encoding the boundary between processed and unprocessed cells as a compact state.