Devlog #90 – Wave 69: Convex Hull, Grover Search, River Meander, Rope Physics, Perceptron & Orbital Resonance

New Simulations

Convex Hull: Three Algorithms, One Stage

The convex hull is the smallest convex polygon enclosing a point set — the algorithmic equivalent of stretching a rubber band around nails on a board. Three classic algorithms approach this differently, and watching them compete on the same input is one of the most instructive things in computational geometry.

Graham Scan O(n log n)

Sort all points by polar angle relative to the lowest point (breaking ties by distance). Then sweep the sorted list: for each new point, pop any hull points that make a clockwise (non-left) turn using the 2D cross product (b−a) × (c−a) = (b.x−a.x)(c.y−a.y) − (b.y−a.y)(c.x−a.x). Collinear points are handled explicitly — the sim lets you toggle whether to include or exclude them from the hull.

Jarvis March O(nh)

Gift-wrapping is intuitive: start from the leftmost point and repeatedly find the point that makes the smallest counterclockwise angle with the current edge. With n total points and h on the hull, this is O(nh) — faster than Graham when h is small, but degrades to O(n²) for circular inputs. The simulation shows a rotating "wrapping arm" arrow at each step.

Quickhull Divide-and-Conquer

Find the leftmost and rightmost points (the base edge). The farthest point from the base line is definitely on the hull — add it and recurse on the two triangular sub-problems. Average O(n log n), worst case O(n²) for adversarial inputs. The recursive subdivision is visualised with colour-coded regions.

• All three algorithms animate simultaneously on the same point set
• Live operation counter per algorithm (comparisons + swaps)
• Preset inputs: random, clustered, circular, adversarial Quickhull case
• Step-through mode to pause at each operation

Grover's Search: Quantum Amplitude Amplification

Classical unstructured search needs O(N) queries to find one marked item among N. Grover's algorithm (1996) does it in O(√N) — a provably optimal quadratic speedup — using only quantum superposition and two simple operators.

Oracle and Diffusion Operators

The algorithm works entirely on real amplitudes (no complex phases needed for one marked item). Each Grover iteration applies:

1. Oracle: flip the sign of the target state amplitude: α_target → −α_target
2. Diffusion: inversion about the mean: α_i → 2μ − α_i where μ is the mean amplitude

The target amplitude grows with each iteration while all others shrink. After k* = ⌊π√(N/M)/4⌋ iterations (M marked items), the success probability peaks near 1. Over-rotating reduces it again — the sim shows this periodic collapse and revival.

Geometric Picture

In the 2D subspace spanned by |marked⟩ and |unmarked⟩, each Grover iteration is a rotation by angle 2θ where sin(θ) = √(M/N). The geometric inset shows this rotation explicitly, making the algorithm's structure immediately clear.

• N from 4 to 128 states; M from 1 to N/2 marked items
• Amplitude bar chart animates in real time
• Success probability vs iteration plot with optimal k* marker
• Classical O(N) expected queries shown for comparison

River Meander: Curvature-Driven Evolution

Rivers don't flow straight for long. A tiny perturbation grows into sinuous meanders as erosion on the outer bank exceeds deposition on the inner bank — a positive feedback loop driven by the centrifugal force of the flowing water.

The Migration Equation

Each node i on the river centreline migrates perpendicular to the flow direction at a rate proportional to a spatially lagged curvature: dn/dt = E₀ · Σ C(s) · κ(s − lag) where κ is the local curvature and the lag accounts for the downstream offset of peak erosion relative to peak curvature. This delayed response is what causes meandering rather than random wandering.

Oxbow Lake Formation

When a meander loop tightens enough that two non-adjacent nodes come within a cutoff distance (proportional to channel width), a neck cutoff occurs: the channel shortcuts across the neck, and the abandoned loop becomes an oxbow lake. The simulation preserves palaeo-channels as faint traces — exactly as they appear in satellite imagery of floodplains.

• Statistics panel: sinuosity ratio (total length / straight distance), oxbow count, dominant wavelength
• Initial perturbation amplitude and migration rate are adjustable
• Time-lapse mode compresses thousands of years of evolution

Rope Physics: Verlet + Jacobi Constraints

Position-based Verlet integration stores only current and previous positions, inferring velocity implicitly as v ≈ (x_now − x_prev) / dt. This makes adding constraints trivial — just correct positions directly without touching velocities, which are then automatically updated.

Jacobi Constraint Relaxation

Each rope segment has a rest length L₀. The constraint correction for a pair of nodes is: move each node toward the other (or apart) by half the length error: Δx = ½ · (d − L₀) · n̂ where d is current distance and n̂ is the unit vector. Running K iterations of this per frame approximates an inextensible rope — K=1 gives stretchy elastic, K=20+ gives stiff rope. The Jacobi (simultaneous) update avoids the directional bias of Gauss-Seidel.

• 5 presets: whip (one pinned end), bridge (two pins), two-pin catenary, free-fall coil, cloth grid
• Drag any node interactively; add cylindrical peg obstacles
• K slider from 1 to 30 iterations per frame
• Gravity direction and magnitude sliders

Perceptron: The Original Neural Network

Frank Rosenblatt's 1957 perceptron is the simplest trainable classifier. It maintains a weight vector w and classifies input x as positive if w·x > 0, negative otherwise. The update rule is elegantly simple: whenever a mistake occurs, nudge the weights in the right direction.

Learning Rule and Convergence

On each misclassified example (y · (w·x) ≤ 0), update: w ← w + η · y · x. The Perceptron Convergence Theorem guarantees this terminates in finite steps if the data is linearly separable — bounded by the square of the margin. The simulation counts mistakes per pass (epoch) and shows this decreasing to zero for separable sets.

The XOR Problem

XOR is not linearly separable — no single hyperplane can divide the four points correctly. The perceptron cycles forever, oscillating between partial solutions. This limitation, highlighted by Minsky and Papert in 1969, motivated the development of multi-layer networks. The sim makes this vivid: the decision boundary spins endlessly on XOR, then snaps to convergence on a Gaussian dataset.

• 5 datasets: two Gaussians, stripe, XOR (fails), circle-in-square (fails), custom (click to add points)
• Decision boundary plane animates in real time
• Mistakes-per-pass graph distinguishes convergence from cycling
• Learning rate η slider

Orbital Resonance: Kepler Rhythms

A resonance occurs when two orbiting bodies complete integer ratios of orbits in the same time, causing repeated gravitational kicks at the same orbital phase. These resonances can stabilise orbits (Jupiter Trojans, Galilean moons) or clear them (Kirkwood gaps in the asteroid belt).

Kepler's Third Law and Resonance Angle

For circular orbits, the period T = a^(3/2) (in appropriate units). A p:q resonance requires T₂/T₁ = p/q, so a₂/a₁ = (p/q)^(2/3). The resonance angle σ = pλ₂ − qλ₁ (where λ is mean longitude) librates around a fixed value if the resonance is active, or circulates through 360° if not. Libration means the planets always meet near the same phase — the kicks are coherent.

Galilean 4:2:1 Three-Body Resonance

The Galilean moons Io, Europa, and Ganymede are locked in a Laplace resonance: for every orbit of Ganymede, Europa completes 2 and Io completes 4. The Laplace angle λ₁ − 3λ₂ + 2λ₃ librates around 180° — the three moons are never all aligned simultaneously. This has prevented catastrophic orbital instability for 4 billion years.

• 6 resonance presets: 1:1, 3:2, 2:1, 5:3, 4:1, and off-resonance comparison
• Conjunction marks (red dots) cluster at the same direction when in resonance
• Resonance angle σ plot shows libration vs circulation
• Galilean preset shows Laplace three-body resonance

Up Next

Wave 70 tackles project management mathematics (CPM/PERT critical path with PERT uncertainty), k-nearest neighbours classification, Euler column buckling with effective-length factors, minimax tree search with alpha-beta pruning, Van Allen belt particle trapping in a dipole field, and Lloyd's relaxation for centroidal Voronoi tessellation.