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

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?

• 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. – orlp Jul 29 at 14:23
• 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. – Discrete lizard Jul 29 at 14:38
• 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. – David Richerby Jul 29 at 14:57
• @orlp you're right, I just got confused with the similarity of the two problems – theshepherd Jul 29 at 16:05
• @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. – theshepherd Jul 29 at 16:08