I am trying to find an algorithm for this. You can imagine each set (S1, S2, …, Sn) as points with different colour. Also it isn’t necessarily |S1|=|S2|=…=|Sn|.

~~For n=1 the problem is simplified into a “Closest Pair” problem, which can be solved with divide and conquer in O(nlogn).~~

For n=1 we trivially have a single (random) point.

For n=2 we have two sets of points S, Q and we seek to find the (distance of the) closest pair of points p, q such as p in S and q in Q. I have also found an efficient algorithm for this, using voronoi diagrams (https://stackoverflow.com/a/13000634/6625377)

For n>2 things get tricky. I have no clue where should I head to. Let’s say we have x red, y green and z blue points laid down in a Euclidian plane. How do we find the minimum distance of a route passing for one red, one green and one blue point?

Is this some special case of the Traveling Purchaser Problem?