Concepts116
Category
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.
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.
Z-Function
The Z-function of a string S computes for each position i the length of the longest substring starting at i that matches the prefix of S.