0
$\begingroup$

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?

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

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.