From Decorative Demo to Real Geometry
The original 2D page for this topic named convex hull, Voronoi diagrams, Delaunay triangulation and closest-pair search in its prose and pseudocode, but its actual "Interactive Demo" never ran any of them — it just scattered random points and flipped a Math.random() < 0.8 "processed" flag on each one. This 3D companion substitutes the genuine mechanics the title promised.
- Convex Hull: a real incremental 3D algorithm — seed tetrahedron, visible-face removal, horizon stitching
- Delaunay Triangulation: the classic paraboloid-lift duality — lower convex-hull faces of lifted points are the real triangulation
- Closest Pair: genuine divide-and-conquer — recursive split plus a distance-bounded strip check
Why 3D convex hull needs a horizon
Adding a point that sees several hull faces at once means those faces have to be replaced together; the boundary between visible and hidden faces (the horizon) is exactly where the new faces attach.
Why the paraboloid lift works
Lifting (x,y) to (x,y,x²+y²) turns "which triangle is locally most equiangular" into "which triangle is on the bottom of a convex shape" — a purely geometric convex-hull question with no angle arithmetic required.
Why divide-and-conquer beats brute force
Splitting the point set in half and only re-examining the thin strip near the split (bounded by the best distance found so far) avoids re-testing pairs that are already known to be far apart.
The mechanics implied by the title, actually running this time — in three dimensions, with a camera you can orbit around the result.