K Clustering
Problem We have set of objects $U = \{o_1, o_2, …\}$, and we want to split them into k clusters.
We also have following definition for distance function.
$\forall_{i,j} dist(p_i, p_j) = dist(p_j, p_j)$ $\forall_{i,j} dist(p_i, p_i) = 0$ $\forall_{i,j} dist(p_i, p_j) > 0$. At the end, we should have $C = \{C_1, C_2, … C_K\}$.
Let’s define spacing to be the minimum dist between clusters. Our goal is to find the k-clustering with maximum spacing.……