# Does this greedy algorithm minimize the sum of the diameters of two clusters?

Suppose given $$2n$$ points in the plane and we want to partition points into two clusters $$C_1$$ , $$C_2$$ such that each cluster contains exactly $$n$$ points and we want to minimize the sum of the diameters of two clusters. The diameter of a cluster is the maximum distance between any two points in that cluster.

I have a greedy algorithm for this problem:

Find diametral pair $$(a,b)$$ of $$2n$$ points, and then consider $$a$$ as the center of $$C_1$$ and $$b$$ as the center of $$C_2$$. Now, we make two lists $$L_a$$ and $$L_b$$ such that $$L_a$$ contains all points sorted by increasing distance from $$a$$ and the other by increasing distance from $$b$$. I keep the first $$n$$ points in $$L_a$$ that are closer to $$a$$ and remove others and then set $$C_1=L_a$$. I do the same for list $$L_b$$ and then set $$C_2=L_b$$.

My question is, the above idea is optimal or not?

I think above idea return optimal solution because I can use Exchange argument as follows:

Suppose in the optimal partitions $$C'_{1}$$ and $$C'_2$$ isn't the same as $$C_1$$ and $$C_2$$ so there exists two points $$c,d$$ such that $$c\in C_1, d\in C_2$$ and $$c\in C'_2, d\in C'_1$$ but according to the algorithm if we exchange $$c ,d$$ we get $$d\in C'_2, c\in C'_1$$ so we achieve a new optimal solution that it's no worse than the optimal solution. So we get contradiction.

Consider the case of the $$4$$ points $$P=\{(0,0), (1,0), (0.5, 0.5), (0.5, 0.5)\}$$. The diametrical points are $$(0,0)$$ and $$(1,0)$$ with distance one. So your algorithm puts them in their own clusters. The closest other-point to $$(0,0)$$ is $$(0.5, 0.5)$$ so your algorithm returns the set $$\{(0,0), (0.5, 0.5)\}$$ and $$\{(1,0), (0.5, 0.5)\}$$ with cost $$\sqrt{0.5^2+0.5^2} + \sqrt{0.5^2+0.5^2}=\sqrt{2}$$.
However, the optimal sets are $$\{(0,0),(1,0)\}$$ and $$\{(0.5,0.5),(0.5,0.5)\}$$ with cost $$1+0=1 < \sqrt{2}$$.