Evaluation indexes hypothesis for clustering I read on the cluster analysis page of wikipedia:

For example, k-means clustering can only find convex clusters, and many evaluation indexes assume convex clusters. On a data set with non-convex clusters neither the use of k-means, nor of an evaluation criterion that assumes convexity, is sound.

I can't see how an evaluation index assumes convex clusters. Can anyone illustrate this idea?
 A: The easiest way to see why the clusters are convex in $k$-means is by appealing to the corresponding Voronoi diagram. If we have $k$ clusters, then there will be $k$ corresponding cells. Let us see how each cell is defined. Let's say that the cluster centers (means) are $\mu_1, \mu_2, \ldots, \mu_k$, all in $\mathbb{R}^d$. Recall that $k$-means uses Euclidean distance. Now, any point that is in cluster 1 must be closer to $\mu_1$ than $\mu_2$. Hence, it must belong to the set
$$
A_{1,2} = \{x \in \mathbf{R}^d: \|x - \mu_1\|^2 \leq \|x - \mu_2\|^2\} ,
$$
which is equivalent to
$$
A_{1,2} = \{x \in \mathbf{R}^d: \|x\|^2 - 2 \langle x, \mu_1 \rangle + \|\mu_1\|^2 \leq \|x\|^2 - 2 \langle x, \mu_2 \rangle + \|\mu_2\|^2\} .
$$
But this is just
$$
A_{1,2} = \{x \in \mathbf{R}^d: \langle x, 2(\mu_2 - \mu_1) \rangle \leq \|\mu_2\|^2 - \|\mu_1\|^2 \} ,
$$
which is a closed half-space.
Now, any point is in cluster 1 if and only if it is in $A_{1,2}, A_{1,3}, \ldots, A_{1,k}$ (where the latter sets are defined analogously). So, the set of points in cluster 1 is an intersection of half-spaces and therefore convex (and the same holds for any other cluster).
