# Split the set of points, algorithm

I'm learning for the test and I can't manage with this problem:

We are given a set of $n < 1000$ points and an integer $d$. The task is to create two disjoint sets of points $A_1$ and $A_2$ (which union is given set of $n$ points) in such way that the distance (euclidean) between each pair of points from $A_i$ (for $i\in\left\{1,2\right\}$) is less or equal to $d$. If it is not possible, print $-1$.

For example, input:

$d=3$, and points:

$(5,3), \ (1,1), \ (4,2), \ (1,3), \ (5,2), \ (2,3), \ (5,1)$

we can create:

$A_1=\left\{ (2,3), \ (1,3), \ (1,1) \right\}$

$A_2=\left\{ (5,3), \ (4,2), \ (5,2), \ (5,1) \right\}$

since each pair of points from $A_i$ (for $i\in\left\{1,2\right\}$) are close enough.

I really want to know how to solve it, but no idea. Since $n$ is small, algorithm can be even $O(n^2\log n)$, but I don't know how to start. I was thinking that maybe start with counting the distance between each pair of points, then take two points with maximum distance and place them in to different sets (if their distance is greater than $d$). Then repeat this step for the rest of pairs, but the problem is how to decide where I can legally put next points. Can anyone help with this algorithm?

-
Hint: Consider the graph in which there is an edge between every pair of points whose distance is not less than or equal to $d$. – Rahul Jan 8 '13 at 23:10
Did you check k-means clustering? Would it apply in this case? – Laurent Jan 8 '13 at 23:12
@RahulNarain, thank you! – xan Jan 9 '13 at 0:14
@Laurent, I'm going to check this, but this term seems very hard. – xan Jan 9 '13 at 0:14

Expanding on Rahul Narain's hint:

Build the graph $G$ where there is an edge between every pair of points whose distance is greater than $d$. Your two sets $A_1$ and $A_2$ correspond to a partition of the vertices so that every edge in the graph goes from $A_1$ to $A_2$. This is exactly the condition that makes $G$ bipartite.

-
Um, the problem is to partition so that elements of $A_1$ are close to elements of $A_2$. You're suggesting a partition where they are far. I think. Hint: Connected components. – Itai Zukerman Jan 8 '13 at 23:58
I was unsure about that myself, but the statement "take two points with maximum distance and place them in to different sets (if their distance is greater than d)" made me go with my interpretation. Hopefully the OP will be back to let us know which is the right one. – Michael Biro Jan 9 '13 at 0:04
I think Michael Biro is right. Yep, $A_1$ are far to $A_2$ but it is irrelevant. We want to have all elements in $A_1$ close to the others from $A_1$ and the same for $A_2$. And I like this idea. So now, the task comes down to graph problem. It's just beautiful! :-) Am I right that to make this partition I only need to color all the vertices of this graph with two colors? And if it works, then I have this partition, if not - the answer is that problem is not solvable? – xan Jan 9 '13 at 0:12
Yes, that's it. – Michael Biro Jan 9 '13 at 0:16
Thank you so much! I am really grateful :-) – xan Jan 9 '13 at 0:17