How can one show a Kmeans solution is unique? Suppose we are given a distribution P and a constant K. We wish to minimize the kmeans objective w.r.t centers ${C1,..Ck}$:

What constraints on $P$ are known to imply that the optimal solution is unique (up to reordering of centers)?
Examples of ad hoc methods would also be appreciated.
In particular intereset to me are continuous distributions.
An example for one-dimensional $P(x)$ and $k=2$ with a unique optimal solution:
$P(X=1)=0.5$
$P(X=-1)=0.5$
The only optimal centers are $C1=1, C2=-1$
 A: K-means is a simplified version of Gaussian Mixture Models (GMM) in that it is equivalent to a GMM with all components having equal variance.  It is useful to think in terms of the variance because your sample distribution is going to have not only central tendency but variational tendency.  I am going to assume at this point that the GMM is appropriate for fitting to the data, that you are not fitting a GMM to non-GMM data.
If your sample data is extremely well behaved, such that the likelihood of a false classification is very low when the cluster centers are placed near the actual centers, then you can have well behaved EM convergence.  The plot of the AIC (or AICc) vs. iteration will tend to converge quickly toward a stable and low value.  If your sample is less well behaved then you can have a number of problematic phenomena including lack of convergence or cycling of the means between some number of center locations.  It is useful to think of Cpk when looking at the variations between clustered components because it is a robust measure of misclassification rate.  It is used in control charts and process control to indicate likely misclassification rates.  
At this point it is very tempting to use some "diffusion-esqe" method in the algorithm to accomplish smoothing of the AIC plot to estimate the point of convergence.  Under-relaxation is simple to implement.  You use EM to compute the updated position of the means, but only move them some small distance toward the new position, then compute again.  This reduces the "noise" some but not entirely.  You will have a new dial, the "learning factor" or "relaxation factor".  This is EWMA on the position of the mean.  
You can use bootstrap resampling within clusters to estimate the variation in the mean for the cluster between EM steps.  If your cluster center stays within the ranged indicated by the resampling for some amount of time then you could assume convergence.
This answer is entirely based on experience, not on theory, and that it gives algorithm directions instead of theoretical proof.  It is somewhat Ad-hoc, so I hope that it has value in that.
A: First problem, the solution is not unique. 
A simple exemple is $P(X=-1)=P(X=0)=P(X=1)= \frac{1}{3}$
This gives:

Depending on initial conditions. We encounter this problem when we have very particular symmetries. In practice this is very rare, almost impossible. 
You may be mixing up this problem with a second one. The convergence of basic k-means  is granted to a local minimum of the cost function, not the global minimum. An exemple from Wikipedia: 

You can adress this problem in many ways: starting near the optimal solution, randomizing the starting points... etc
While the uniqueness of the optimal solution is almost sure, you may end up with many local solutions.
