# How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?

Question 1:

Given N sets of points $$S_1$$ ... $$S_n$$ (no intersection between $$S_i$$ and $$S_j$$ when i != j),

I want to find subsets of $$S_1$$ ... $$S_n$$ (call them $$T_1$$ ... $$T_n$$ respectively)

So that for any point in $$S_k$$ ,the nearest neighbor to it in $$\bigcup_{i=1}^{n} T_{i}$$ is in $$T_k$$,

Obviously $$T_k$$ = $$S_k$$ (k= 1 ,...,n) could suffice .

Now how to find the subsets $$T_1$$ ... $$T_n$$ so that | $$\bigcup_{i=1}^{n} T_{i}$$ | is minimum ?

Question 2:

Given N sets of points $$S_1$$ ... $$S_n$$ (no intersection between $$S_i$$ and $$S_j$$ when i != j),

I want to find point sets $$T_1$$ ... $$T_n$$ (no intersection between $$T_i$$ and $$T_j$$ when i != j, $$T_k$$ may or may not be subset of $$S_k$$ )

So that for any point in $$S_k$$ ,the nearest neighbor to it in $$\bigcup_{i=1}^{n} T_{i}$$ is in $$T_k$$,

Obviously $$T_k$$ = $$S_k$$ (k= 1 ,...,n) could suffice .

Now how to find the subsets $$T_1$$ ... $$T_n$$ so that | $$\bigcup_{i=1}^{n} T_{i}$$ | is minimum ?

(Distance can be any kind of Minkowski distance ,like Manhattan distance , Euclidean distance, or Chebyshev distance)