Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm a working software engineer faced with the following problem: I have a set of points on a 2d plane. Each point can have one of $k$ different colours. I wish to select one point of each colour that are "as close as possible". To formalize that a bit, let's say that they are all covered by a circle with the smallest possible radius.

I have one idea for a solution: Fix some point $p$ in the set of points. For each colour $c$, choose a point of colour $c$ that is closest to $p$. Do this (from scratch) for every point p, and eventually take the solution with minimum radius.

The question I'm faced with now is: How good a solution is this? Does it find the exact answer? Is it an approximation? If so, what is it's approximation ratio?

Edit: So this has a counterexample. The question is then is this a good approximation?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Consider the following diagram, which illustrates a case in which the algorithm you describe will not find the exact answer.

enter image description here

We see that the green circle is the smallest possible circle that contains a point of every color. However, each point in the circle has some color for which the point in the circle is farther away than some point outside the circle. Therefore the algorithm will fail to find the green circle. In fact, in this extremely contrived case the algorithm will find the largest circle that contains exactly one point of each color (but only because there are two circle sizes with this property).

As for how good of an approximation it is, that depends on the particular case; I expect that an average case analysis would be extremely difficult. For what it's worth, this seems like a problem for which a greedy algorithm like this one won't be a particularly good approach.

Here's a very vague idea for an alternative. Start with the circle around all points in the set, and think about a way to systematically throw out points that have duplicate colors until no more points can be thrown out without losing a color in the circle. This may be a better way to find the minimum radius.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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