Given $n=2k$ points in the plane and also given positive real value $r$. Is there an algorithm that partition points into two groups $G_1$ and $G_2$ such that each group contains exactly $k$ points and also distance between each pair of points in $G_1$ has distance at most $r$?
I seek for an algorithm that solve above problem on $o(n^2)$ or a proof that show us we can't solve above problem in less than $\Omega(n^2)$.
