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

CC BY-SA 4.0
2022-04-13T22:04:22.413Z
Possibly related: comments following https://cstheory.stackexchange.com/questions/51118/a-problem-in-understanding-an-algorithm (including link to now-deleted https://cstheory.stackexchange.com/questions/51279/partition-points-into-two-equal-clusters)
Neal Young
CC BY-SA 4.0
2022-04-14T00:20:02.397Z
@NealYoung Thank you in advance. Could you give me some hint about this problem?
TAre
<ds.algorithms><computational-geometry>
Partition points in the plane
TAre
# Partition points in the plane

(Asked by: username_0 on 2022-04-12)

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

**Tags:** ds.algorithms, computational-geometry

> **Comments:**
> **username_1**: Possibly related: comments following https://cstheory.stackexchange.com/questions/51118/a-problem-in-understanding-an-algorithm (including link to now-deleted https://cstheory.stackexchange.com/questions/51279/partition-points-into-two-equal-clusters)  
> **username_0**: @NealYoung Thank you in advance. Could you give me some hint about this problem?  

---

## 0 answers

