SSE between two consecutive iterations drops below a threshold, i.e., $ {{\left( {\mbox{SSE}_{i - 1} - \mbox{SSE}_i} \right)} \mathord{\left/ {\vphantom {{\left( {\mbox{SSE}_{i - 1} - \mbox{SSE}_i} \right)} {\mbox{SSE}_i}}} \right. \kern-\nulldelimiterspace} {\mbox{SSE}_i}} \leq \varepsilon $, where $\mbox{SSE}_i$ denotes the SSE value at the end of the $i$-th ($i \in \{ 1, 2, \dotsc, 100 \}$) iteration. The convergence threshold was set to $\varepsilon = 10^{-6}$.

In this study, we focus on IMs that have time complexity linear in $N$. This is because k-means itself has linear complexity, which is perhaps the most important reason for its popularity. Therefore, an IM for k-means should not diminish this advantage of the algorithm. The proposed methods, named Otsu Var-Part (`OV`) and Otsu PCA-Part (`OP`), were compared to six popular, linear, order-invariant IMs: Forgy’s method (`F`), MacQueen’s second method (`M`), maximin (`X`), k-means++ (`K`), Var-Part (`V`), and PCA-Part (`P`). It should be noted that among these methods `F`, `M`, and `K` are random, whereas `X`[^2], `V`, `P`, `OV`, and `OP` are deterministic.

We first examine the influence of $L$ (number of histogram bins) on the performance of `OV` and `OP`. Tables \[tab\_num\_bins\_var\] and \[tab\_num\_bins\_pca\] show the initial and final SSE values obtained by respectively `OV` 