Computational Geometry

The sign of a single 2D cross product tells you whether three points turn left, turn right, or are collinear, and that one signed scalar is the workhorse behind almost every algorithm in the plane. Convex hulls, polygon area, segment intersection, and point-in-polygon tests all reduce to a sequence of cross-product evaluations with a careful eye on edge cases. Get the geometric primitive right and the rest of the field follows. **Computational Geometry** introduces those primitives and the algorithms built on them. You will start with cross products and the orientation test, then implement convex-hull algorithms three ways: Graham scan in `O(n log n)` (sort by polar angle, maintain a stack with the orientation invariant), Jarvis march in `O(nh)` for hulls with few vertices, and Andrew's monotone chain. The lesson then covers line-segment intersection, the sweep-line algorithm for many segments, the closest-pair-of-points algorithm in 2D, polygon computations using the Shoelace formula, and the ray-casting point-in-polygon test. In **Sorting (Elementary)**, you learned the comparison-based sorting that drives polar-angle preprocessing. **Divide and Conquer (Advanced)** taught you the closest-pair `O(n log n)` template via the strip combine step, which reappears here. Next, **Advanced Tree Algorithms** moves from planar geometry back to hierarchical structures with Binary Lifting and centroid decomposition.

Multiplying two `n`-bit integers the way you learned in school takes `O(n^2)` digit operations. In 1960, Karatsuba showed that the same product can be computed with three recursive multiplications instead of four, dropping the cost to `O(n^1.585)`. A few years later Strassen pulled the same trick on matrix multiplication, replacing eight recursive multiplications with seven and breaking the `O(n^3)` barrier for the first time. Both algorithms are pure divide-and-conquer with cleverly engineered combine steps, and they remain the gateway to a deeper view of D&C as algebraic restructuring. **Divide and Conquer (Advanced)** walks through that view. You will derive Karatsuba multiplication and apply the Master Theorem to its `T(n) = 3T(n/2) + O(n)` recurrence. You will work through Strassen's seven-multiplication identity for `2 x 2` blocks and discuss when its higher constant factor pays off in practice. You will solve closest-pair-of-points in 2D in `O(n log n)` via the strip optimization in the combine step, and look at convex-hull computation through a divide-and-conquer lens. In **Divide and Conquer (Intro)**, you applied the Master Theorem to merge sort and quick sort. **Recursion Fundamentals** gave you the call-stack model these algorithms still inhabit. This lesson keeps the recurrence framework but engineers cleverer combine steps. Next, **Mathematical Algorithms** turns to number-theoretic computation.