Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

Question

I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$.

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 that $p\in S$ and $q \in Q$. I have also found an efficient algorithm for this, using voronoi diagrams.

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 an 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?

• orlp: I disagree with your $n = 1$ solution, surely just presenting a single point is the solution, as the trivial path starting and ending on itself is the shortest and contains a point from each set once.
• Discrete lizard: This seems to be a generalization of a variant of TSP (where we have a path instead of a tour), because it seems your problem reduces to finding a shortest path visiting $n$ nodes if $|S_i|=1$ for all $i\leq n$. So your problem in general appears to be at least as hard as TSP. I don't know whether this particular generalization has been studied, however.
• David Richerby: I don't understand your question. You've given two special cases but I don't see what general property you're looking for. Why is it that, with one set, I need to find a pair of points within that set but, with two sets, I need to find a path between the sets? What am I supposed to do with three or four sets? Please give a formal definition of the problem, rather than hoping that we can generalize two near-trivial examples.
• theshepherd: @orlp you're right, I just got confused with the similarity of the two problems
• theshepherd: @DavidRicherby sorry if I wasn't clear. The problem statement is briefly (but accurately in my opinion) described in the title. The examples are here both to explain further and to summarize what I have found so far.

Answer 1

This problem is a generalization of TSP known as Set TSP. Not surprisingly, it is both NP-complete and well-studied.