a probability of $\frac{{md\left( {{{\bf x}}'} \right)^2 }}{{\sum\nolimits_{j = 1}^N {md({{\bf x}}_j)^2 }}}$, where $md({{\bf x}})$ denotes the minimum-distance from a point ${{\bf x}}$ to the previously selected centers. This method yields an $\Theta(\log{K})$ approximation to the MSSC problem.

The PCA-Part method [@Su07] uses a divisive hierarchical approach based on PCA (Principal Component Analysis) [@Hotelling36]. Starting from an initial cluster that contains the entire data set, the method iteratively selects the cluster with the greatest SSE and divides it into two subclusters using a hyperplane that passes through the cluster centroid and is orthogonal to the principal eigenvector of the cluster covariance matrix. This procedure is repeated until $K$ clusters are obtained. The centers are then given by the centroids of these clusters. The Var-Part method [@Su07] is an approximation to PCA-Part, where the covariance matrix of the cluster to be split is assumed to be diagonal. In this case, the splitting hyperplane is orthogonal to the coordinate axis with the greatest variance.

Figure \[fig\_varpart\_ruspini\] illustrates the Var-Part procedure on a toy data set with four natural clusters [@Ruspini70]. In iteration $1$, the initial cluster that contains the entire data set is split into two subclusters along the Y axis 