Every other course on this path measures an algorithm. This one measures a PREDICATE: the same orientation test in exact integers and in double precision, on 29 magnitudes of the same input, with the wrong answers counted rather than warned about. The failure turns out to have a shape — the rounded test can lose a turn and provably cannot invent the opposite one — and the rest of the course is what that sign is used for, with degenerate input treated as the subject rather than excluded from it.
Overview
By the end you can reduce a geometric question to the sign of a determinant, say at what magnitude a floating-point version of that determinant stops being reliable and what its failure can and cannot look like, handle collinear and duplicate input as cases with answers rather than as input to reject, and read every count on these pages as a measurement of the points on screen.
Side of a line, segment crossing, polygon orientation, hull corner, and the comparison that drives a rotating caliper — each written as a determinant compared against zero, with no division, no square root and no angle anywhere.
Derive the 2k > 53 threshold from the width of a double's significand, read the swept count off the page as a measurement of a constructed family, and prove that a rounded orientation can only collapse to zero — so a hull can lose a vertex and cannot gain one.
Three collinear points, a duplicate point, a hull that is a segment, a segment that is a point, a ray through a vertex, two collinear segments with identical signs and opposite answers. Each is a case with a right answer, and in one of them three correct procedures give 4, 6 and 8.
Every figure on these pages comes from running the algorithm on the input shown. Three pages here have the measured column and the proved bound disagreeing sharply — 5 strip comparisons against 84, 36 wrapping comparisons against a reference of 27, and a sweep that makes every test the brute force makes — and each one says which number is which.
Lessons
The determinant first, then the magnitude at which a floating-point version of it loses the sign, then the corner that costs; then hulls, where a collinear point produces three different right answers, and the diameter the hull makes cheap; then segments, where four signs settle the easy case and two inputs with identical signs have opposite answers; and last area, inside, and distance, where the measured column and the proved bound sit furthest apart.
Discrete Mathematics in full, and by name: Big-O, Big-Omega and Big-Theta, Analysing Iterative Algorithms, Recursion Trees and the Master Theorem, Loop Invariants and Program Correctness, and Strong Induction, which every proof here uses. From Algebra, The Coordinate Plane, and the 2×2 determinant, which is defined inline on the opening page so that a reader who has not taken Algebra's course on systems and matrices loses nothing. From this path: Data Structures, for the sorted order a sweep line maintains and the balanced tree behind it; Sorting and Selection, whose comparison count is quoted here and re-derived nowhere, and whose lower bound is what the convex-hull reduction is a reduction to; and Graph Algorithms, for nothing beyond the habit of putting a measured count beside a proved bound.
Type the near-degenerate worked example before the ordinary one. Every lab on this course opens on a case chosen to be interesting, and the preset lists are ordered so that the textbook input comes first and the input that breaks the textbook method comes later. A reader who only ever looks at the first entry will see a course in which nothing goes wrong.
Change one control at a time and watch which figures move. The hull page runs both predicates on every redraw, so the two vertex counts are always side by side; the sweep page's status list is what explains its pair-test count; the polygon page's sign flips when you reverse the vertex order and the area does not. A figure that moves with a control you did not expect to matter is the most useful thing on the page.
Read every count as a fact about the points on screen. The sweep saves twelve pair tests out of fifteen on one input and none out of six on another; gift wrapping does 36 comparisons against a reference of 27 on the nine points the hull page opens with, and 72 against 96 on 24 points with only three on the hull. None of those is a property of an algorithm, and every page that prints one says so.
Voronoi diagrams, Delaunay triangulation, and the lifting to a paraboloid that connects them to hulls in three dimensions. The lifting of points to a parabola appears here only as the reduction that gives the convex-hull lower bound; the structures themselves are a course of their own and nothing on this one depends on them.
Linear programming in fixed dimension, smallest enclosing circles, and the randomised incremental methods that solve both in expected linear time. They are geometry and they are also an application of the probabilistic analysis this path develops later, so they belong beside that rather than here.
Floating-point filters and adaptive exact arithmetic — evaluating a predicate in doubles with an error bound and falling back to exact arithmetic only when the bound is too loose to decide. It is what production geometry kernels actually do, and it is a numerical-analysis argument rather than a geometric one; these pages compute every predicate exactly and say so.
Geometry in three or more dimensions, and range-searching structures. A k-d tree and a two-dimensional range query are in the kit this course draws on and no lesson here uses them: the pruning a range query achieves is a property of the window rather than of the tree, which is the same lesson the sweep-line page already carries, and building the tree is a balanced-search-tree question that Data Structures owns.