This is a question I originally posted to math.stackexchange.com but it didn't attract any answers, and I was wondering if someone here can help.
Consider a unit vector $x\in\mathbb R^d$ ($\|x\|_2=1$), and a $k$-means clustering of it for $k=2$.
How big can the within-cluster sum of squares get?
Formally:
How to upper bound $$ \max_{\|x\| = 1}\min_{\mu_1,\mu_2\in\mathbb R} \left(\sum_{i=1}^d\min\left\{\left(x_i-\mu_1\right)^2,\left(x_i-\mu_2\right)^2\right\}\right)\quad ? $$
A trivial bound is $1$, but I suspect a much tighter bound exists.
It's easy to show that this quantity is at least $1/4$, by considering $x$ for which third of its coordinates are proportional to $1$, third to $-1$, and third are zeros (e.g., $x=(1/\sqrt 2, -1/\sqrt 2, 0)$ if $d=3$).
