Lloyd's Relaxation: Watching a Boundary Self-Smooth
Each Lloyd step replaces every boundary vertex with the centroid of its two neighbors, which smooths local noise and pulls every vertex toward the same distance from the centroid, so the boundary converges to a circle and stops.
A complete interactive classroom, not just a preview.
Start when you are ready to enter this Stage's 8 scenes and explore, respond, and learn as you go.
How does Lloyd's iteration reshape a closed boundary step by step until it reaches a state where nothing changes?
Start with a jagged, wobbly closed curve and watch it settle into a perfectly rounded shape in only a handful of steps.
Intuition suggests that pulling points sideways to a shared average should shrink a shape inward — so why does Lloyd's iteration instead march toward a clean, uniform circle instead of collapsing it?
A side-by-side, step-by-step visualization showing a polygon boundary evolve through iterations (k=0, 1, 2, 3, 10) until it stabilizes.
Each iteration replaces every point with the centroid of its neighbors, which simultaneously smooths the curve and shifts vertices outward toward a uniform radius — the loop ends only when every move becomes zero.
A reasonable first guess is that averaging neighboring points would only contract the curve inward and never stabilize, so the loop would keep shrinking until the shape vanishes.
- Voronoi diagram construction mechanics
- Surface meshing in 3D
- Weighted or constrained Lloyd variants
- Convergence proofs with error bounds
- 01A Boundary That Keeps ChangingslideQuestion
Open with a jagged polygon and ask the driving question: how does repeatedly averaging neighbors reshape it step by step until it stops moving?
- Show a closed polygon with deliberately uneven spacing and sharp corners
- State the driving question on screen so the rest of the exploration answers it
- Frame Lloyd's iteration as the local rule 'replace each point by the midpoint of its neighbors'
- 02Predict What One Step DoesinteractivePrediction
Let the learner drag vertex positions on a closed polygon and watch one Lloyd step execute, isolating the local averaging rule before committing to a global prediction.
- Drag any vertex and click 'Apply Lloyd Step' to see the immediate effect
- Observe that each new point sits between its two neighbors, never overshooting
- Use the visible moves to motivate the quiz prediction about long-term shape
- 03Your Long-Run PredictionquizTransfer
After seeing one step, the learner commits to what shape the boundary approaches after many iterations.
- Make one independent choice before the explanation
- 04Five Iterations Side by SideslideEvidence
Show the same starting polygon at iterations 0, 1, 2, 3, and 10 so the learner can directly compare progression without speculation.
- Display five overlaid or sequentially drawn copies of the evolving polygon
- Highlight that sharp corners round out first while overall size barely changes
- Show that by iteration 10 the boundary is indistinguishable from a circle
- 05Track the Radius Over StepsinteractiveEvidence
Run the iteration live and plot every vertex's distance to the centroid at each step, making the convergence to one value visible as data.
- Plot radius-to-centroid against iteration count for the redrawn polygon
- Watch the spread of distances collapse toward a single horizontal line
- Identify the iteration number after which all radii are within a tight tolerance
- 06Why the Curve Rounds Instead of ShrinkingslideExplanation
Explain the two competing effects inside each midpoint step: local smoothing removes high-curvature corners, while the same arc length redistributes outward to keep perimeter stable.
- Replacing a vertex with its midpoint moves that vertex inward on convex corners, smoothing them
- Shorter sides pull their endpoints inward less than long sides push outward, equalizing side lengths
- With equal side lengths on a closed curve, the boundary lies on a circle centered at the centroid
- Once every vertex sits on that circle, the centroid of any two neighbors already lies on the same circle, so the next step changes nothing
- 07When the Rule Stops WorkingslideBoundary
Show one configuration where midpoint averaging either does not converge to a circle or behaves pathologically, marking the edge of the explanation.
- Demonstrate a self-intersecting polygon where averaging collapses a crossing before rounding
- Show that a polygon with only 3 or 4 vertices can lock onto a non-circular equidistant shape on its first few steps
- Clarify that the smoothing-to-circle behavior is asymptotic and assumes a fine, well-behaved starting mesh
- 08The Loop Halts on a CircleslideResolution
Directly answer the driving question by restating the rule, its smoothing effect, and the precise fixed-point condition where the boundary stops changing.
- Each Lloyd step replaces every vertex with the centroid of its two neighbors
- Sharp features smooth out, side lengths equalize, and every vertex drifts toward the same distance from the centroid
- The boundary converges to a circle, and the process stops when no vertex moves on the next step
Discussion threads for a Stage aren't available yet.
