Lesson 287
Computational Geometry
Orientation · Convex Hull · Sweep Line
1:00How a single cross-product primitive — orient(A, B, C) — powers convex-hull construction, segment intersection, and closest-pair detection, all in O(n log n) with no trigonometry.
By the end, you can
- Explain what orient(A, B, C) computes and interpret its sign as a left turn, right turn, or collinear result.
- Compute the 2-D cross product by hand for given coordinates.
- Trace the monotone chain algorithm on a small point set, identifying which points get popped and why.
- State the time complexity of monotone chain and explain which step dominates.
- Describe the sweep-line paradigm: what the event queue holds, what the active set is, and why testing only adjacent pairs suffices.
- Compare the O(n²) brute-force approach for segment intersection with the O(n log n) sweep-line approach and explain the savings.
Up next in String Algorithms, Advanced DP & Competitive Techniques
