Algorithms · Cluster
Computational Geometry
Convexity, intersections, and spatial queries.
- 01 Convex Hulls by Monotone Chain How a lexicographic sort followed by two stack scans produces the convex hull in O(n log n), and why the collinearity rule decides which points survive.
- 02 Point in Polygon: Crossing Number and Winding Number Why two standard containment tests disagree on self-intersecting polygons, how each handles rays through vertices, and what the boundary rule costs.
- 03 Detecting Segment Intersections with Orientation Tests How four orientation signs decide whether two segments cross, why the collinear cases need separate handling, and where the all-pairs test stops being affordable.
- 04 Exact Geometric Predicates and Adaptive Precision Why the sign of a determinant is the fragile part of computational geometry, how error bounds let a fast float path stay exact, and when exact arithmetic becomes unavoidable.
- 05 Bentley–Ottmann: Reporting All Crossings with a Sweep Line How a moving vertical line reduces segment intersection from all-pairs to neighbour checks, which events drive the sweep, and why degeneracies make the textbook algorithm hard to ship.
- 06 Delaunay Triangulation and the Empty Circumcircle Test Why maximising the minimum angle reduces to a single determinant test, how incremental insertion repairs the mesh locally, and what happens when four points share a circle.
- 07 Fortune's Sweep and the Beach Line of Parabolic Arcs How a moving line and a growing chain of parabola arcs produce the Voronoi diagram in O(n log n), and why circle events are the subtle part.
- 08 k-d Trees for Range Search and Nearest Neighbours How median splits over alternating axes turn a point set into a pruning structure, what the O(√n + k) range bound really assumes, and why high dimensions break it.
- 09 Trapezoidal Maps and Randomized Point Location How a planar subdivision becomes a DAG of trapezoids that answers containment queries in expected O(log n), and why the search structure is a second, separate object.
- 10 Separating Axes and Support Functions for Convex Intersection Tests How the Minkowski difference turns two convex bodies into one, why a finite set of axes suffices for polygons, and how GJK searches the difference without building it.