Suppose a cluster of points needs one location to represent it. Its centroid is its center of mass: compute each coordinate as the mean of that coordinate across the points. More generally, a center of mass uses a weighted combination of coordinates; the point-based implementations here use ordinary means. A centroid need not be one of the original points. section 10.3 section 10.3.3 section 12.2
For an SS-tree node, the centroid locates the center of its spherical bounding envelope. Compute it from the node’s points if the node is a leaf, or from its children’s centroids if it is internal. Then choose a radius that covers the entries: the greatest centroid-to-point distance for a leaf, or the greatest centroid-to-child-centroid distance plus that child’s radius for an internal node. Recompute the envelope after insertion or a split. section 10.3 section 10.3.3 section 10.3.2
Choosing where to insert a point
At each internal SS-tree node, measure the new point’s distance to every child centroid and follow the closest child. This visits one root-to-leaf path, giving the stated O(log_M n) bound for that traversal. It is a heuristic: the chosen leaf may need to expand and overlap a leaf that already covered the point. section 10.3.2 section 10.3.3
In k-means, start with k centroids, assign each point to its nearest centroid, and replace each centroid with the center of mass of its assigned points. Repeat until assignments stop changing or an iteration limit is reached. The coordinate-by-coordinate update is straightforward, but the overall result depends strongly on initial centroids; random restarts help compare alternatives. With n points, k centroids, d dimensions, and m iterations, the stated total running time is O(mknd), with O(n+k) extra memory. section 12.2 section 12.2.3
Figure 12.3 An example of the k-means algorithm with k==3. Dataset points are initially lightly shaded. Step 1: k centroids (shaped as pentagons) are randomly created. Each centroid is assigned a different color: RGB. Step 2: For each point, measure the distance to all centroids, and assign the point to the closest one. At the end, each centroid C will define a cluster, a sphere centered at C and whose radius is the distance to the furthest point assigned to C. The clusters are highlighted in the same color as their centroids. Step 3: Update the centroids: for each cluster, compute its center of mass. Step 4: Repeat steps 2 and 3 j times. Some points will switch to a different cluster.
The diagram tracks three centroids through assignment and recentering, making the changing cluster centers visible. section 12.2
A centroid is not necessarily the center of the smallest sphere enclosing its points. Moving a sphere’s center can shrink its required radius, although computing an exact smallest enclosing sphere in higher dimensions is costly. Centroid-based methods also have limits: outliers pull means away from otherwise representative positions, and nearest-centroid assignment struggles with non-spherical clusters. section 10.5.2 section 12.2.1
