1
$\begingroup$

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)

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Browse other questions tagged .