23 of 23 Parts Published -- Complete!
Main Parts
The core 23-part path: planar primitives and predicates, sweep lines and subdivisions, optimization and spatial searching, point location and duality, then higher dimensions, visibility, and motion planning.
Part 1
Geometric Modeling, Predicates, and Robustness
Points, orientation, and the exact-answer test every later algorithm in this series depends on.
Read Article →Part 2
Intersections, Distances, and Point-in-Polygon Queries
Segment intersection, point-to-segment distance, and point-in-polygon tests -- all built on Part 1's orientation predicate.
Read Article →Part 3
Convex Hulls in the Plane
Brute force to Graham scan and Andrew's monotone chain, and the sorting lower bound they meet exactly.
Read Article →Part 4
Closest Pair and Geometric Divide and Conquer
The O(n log n) closest-pair algorithm and the packing argument that bounds its strip check to O(n).
Read Article →Part 5
Rotating Calipers and Convex-Polygon Optimization
Antipodal pairs on a convex hull answer diameter, width, and minimum-area enclosing rectangle in O(n).
Read Article →Part 6
Sweep-Line Algorithms and Segment Intersection
An event queue and ordered sweep status turn a quadratic all-pairs scan into local neighbor checks.
Read Article →Part 7
Planar Subdivisions and the Doubly Connected Edge List
Half-edges, twins, and next/prev links -- the topology structure overlay and triangulation build on.
Read Article →Part 8
Subdivision Overlay and Polygon Boolean Operations
Split, merge, label, and select faces to compute union, intersection, difference, and XOR.
Read Article →Part 9
Polygon Triangulation, Monotone Decomposition, and Art-Gallery Guards
Ears, monotone sweep decomposition, and the 3-coloring argument behind the floor(n/3) guard bound.
Read Article →Part 10
Half-Plane Intersection and Low-Dimensional Linear Programming
Feasible regions, randomized incremental LP, and the tiny-basis idea behind LP-type problems.
Read Article →Part 11
Orthogonal Range Searching: Kd-Trees and Range Trees
Preprocess points once, then answer rectangular window queries by kd-tree pruning or layered range trees.
Read Article →Part 12
Interval, Segment, and Priority Search Trees
Stabbing, overlap, windowing, and three-sided queries -- one canonical-subset idea, three specialized trees.
Read Article →Part 13
Simplex Range Searching and Partition Trees
When queries aren't axis-aligned: simplicial partitions bound how many groups any hyperplane can cross.
Read Article →Part 14
Quadtrees, Spatial Decomposition, and Mesh Generation
Recursive spatial cells that double as an index, a multiresolution picture, and a mesh skeleton.
Read Article →Part 15
Trapezoidal Maps and Randomized Point Location
Randomized incremental segment insertion and a history DAG that answers point-location queries in expected O(log n).
Read Article →Part 16
Voronoi Diagrams and Nearest-Site Geometry
Bisectors, empty circles, unbounded cells, segment sites, and farthest-point structure.
Read Article →Part 17
Delaunay Triangulations and Randomized Incremental Construction
Empty circumcircles, legal flips, conflict cavities, and robust randomized insertion.
Read Article →Part 18
Geometric Duality, Line Arrangements, Levels, and Discrepancy
Trade points for lines, above for below, and turn incidence questions into order questions.
Read Article →Part 19
Convex Hulls and Half-Space Intersection in 3D
Visible faces, horizon cycles, and conflict graphs -- randomized incremental construction lifted into 3D.
Read Article →Part 20
Binary Space Partitions and the Painter's Algorithm
Recursive space splitting that supplies a viewpoint-dependent back-to-front drawing order.
Read Article →Part 21
Configuration Spaces, Minkowski Sums, and Translational Motion Planning
Turn a moving polygonal robot into a point navigating obstacles expanded by its reflected shape.
Read Article →Part 22
Visibility Graphs and Euclidean Shortest Paths
Why an optimal route only bends at obstacle vertices, and how to search the graph that proves it.
Read Article →Part 23
Choosing, Testing, and Engineering Geometric Algorithms
Arithmetic policies, workload tradeoffs, adversarial tests, and reproducible evidence -- the series finale.
Read Article →6 of 10 Spotlights Published
Algorithm Spotlights
Focused, single-algorithm traces: Graham scan, Andrew's monotone chain, closest pair, rotating calipers, Bentley-Ottmann sweep line, and more.
Spotlight
Graham Scan
A full worked trace of the polar-angle-sort-and-stack convex hull algorithm.
Read Article →Spotlight
Andrew's Monotone Chain Convex Hull
Sort by coordinate, not angle, and build the lower and upper hulls with the same left-turn stack.
Read Article →Spotlight
Closest Pair of Points
The full O(n log n) divide-and-conquer implementation, with the strip check traced step by step.
Read Article →Spotlight
Rotating Calipers
Walking antipodal pairs around a convex hull to compute its diameter in O(n).
Read Article →Spotlight
Bentley–Ottmann Sweep Line
An event-by-event trace of output-sensitive segment-intersection reporting, stale events included.
Read Article →Spotlight
Sutherland–Hodgman Convex Clipping
Four inside/outside cases and one line: clipping a polygon against a convex window edge by edge.
Read Article →3 of 7 Deep Dives Published
Deep Dives
Cross-cutting topics referenced throughout the series: exact arithmetic and robustness, output-sensitive lower bounds, fractional cascading, randomized algorithms, and dynamic/kinetic and high-dimensional extensions.
Deep Dive
Exact Arithmetic, Adaptive Precision, and Simulation of Simplicity
Why the orientation and in-circle predicates need more than double-precision floats to be trustworthy.
Read Article →Deep Dive
Fractional Cascading
One binary search, then constant-time navigation across every remaining sorted catalog.
Read Article →Deep Dive
Randomized Algorithms in Computational Geometry
Random permutations, backward analysis, and why 'expected time' needs more care than the slogan suggests.
Read Article →3 of 3 Capstones Published -- Complete!
Capstone Projects
End-to-end builds combining multiple parts: a GIS overlay engine, a proximity and terrain toolkit, and a polygonal-robot route planner.
Capstone
A GIS Overlay and Spatial Query Engine
Robust predicates, a sweep line, a DCEL, polygon overlay, range trees, and point location combined into one small GIS engine.
Read Article →Capstone
Proximity and Terrain Toolkit
Convex hulls, closest pair, Voronoi/Delaunay duality, barycentric interpolation, and quadtree indexing in one toolkit.
Read Article →Capstone
Polygonal Robot Route Planner
Minkowski sums, configuration-space obstacles, visibility graphs, and certified shortest-path routes -- the series finale.
Read Article →