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)$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.