Finding Groups

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?

More shops always means shorter trips… but each shop costs money. Look for the "elbow" where adding one more stops helping much.

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?

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 choosing k.
  • 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.