k-means alternates two steps: assign every point to its nearest centre, then update every centre to the mean of its points. Each step can only lower the objective J = Σ |x − c|², so the algorithm stops after finitely many steps, but possibly in a local minimum. k-medoids uses data points (medoids) as centres and any distance; the alternating version follows the book's description, while PAM (BUILD then SWAP, the algorithm of cluster::pam) tries every exchange of a medoid with a non-medoid and makes the best one. The right panel records the objective after every step.
The poor start puts all k seeds in the lower-left group of the simulation (rows 5, 17, 33, 48, ... of the data, R numbering). A random start uses k distinct data points chosen by a seeded generator, so everyone sees the same run. PAM does not need a start: BUILD chooses the first medoid as the point with the smallest total distance to all others, then adds the point that lowers the total most, until there are k.
code/ch05_clustering.R (Figure 5.12).