Pizza Shop Planner
You're opening pizza shops in a little town. Where should they go so every pizza arrives hot? Nobody tells the robot where the neighbourhoods are — it has to find them by itself.
Every little house wants pizza! I dropped my shops in random spots. Let's move them so delivery trips get shorter. Press Step 1 to start.
Drag on empty land to build houses · drag a pizza shop to move it somewhere silly
Snapshots each round
A photo of the town after each round. Tap one to look back.
How many shops is worth it?
How it works
Drop the shops
Put the shops anywhere to start. One shop for each group we want.
Houses pick a shop
Every house orders from the shop that is closest to it.
Shops move to the middle
Each shop moves to the very middle of all the houses that ordered from it.
Repeat until calm
When no house wants to switch shops any more, the neighbourhoods are found!
What just happened?
- Nobody told the robot where the neighbourhoods were — there were no answers at all.
- It just repeated two simple steps: pick nearest shop, move shop to the middle.
- Every round the average trip got shorter, until nothing changed.
- The groups it found are the neighbourhoods. That's finding groups (clustering)!
- Bad starting spots can get stuck in a so-so answer — try again with new spots.
For grown-ups: what's really going on
This is k-means clustering (Lloyd's algorithm), the classic unsupervised learning method. Houses are unlabeled 2-D points; shops are centroids.
- Assignment step: each point joins the nearest centroid (Euclidean distance). The tinted regions are the resulting Voronoi cells.
- Update step: each centroid moves to the mean of its points.
- k-means minimises inertia
Σ ‖xᵢ − μ_c(i)‖²(squared distances). The "average trip" shown is the plain mean distance, which is easier to read; it falls along with inertia in practice. Both steps never increase inertia, so the algorithm converges — but only to a local minimum; drag a shop to a silly spot to see one. - The "1 to 8 shops" chart uses k-means++ initialisation with restarts per
k; the highlighted bar is the elbow (farthest point from the chord), a heuristic for choosingk. - River town shows k-means' assumption of round-ish blobs; density-based methods like DBSCAN follow curved shapes better. (Real facility-location problems also weigh roads and costs.)
Further reading: Naftali Harris, "Visualizing K-Means Clustering" · scikit-learn "Clustering" user guide.