Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Facts: n points in the plane, each has one of k colors, all k colors are represented.

Problem: You wish to select k points, one of each color, such that the perimeter of the convex hull is as small as possible.

Greedy algorithm: For each point p, for each color c not equal to p, select the point of color c closest to p. In the end, choose the point set that has a convex hull with the smallest diameter (diameter is the distance between the two points furthest apart.)

Why is the approximation ratio $\pi/2$?

This was an exercise on my graduate level algorithms exam. We were only given a few lines to answer so it should be simple enough, but I do not know where to start.

share|cite|improve this question

Here is a suggestion as to where to start. Suppose that the optimal solution has diameter $D$. Its optimal value is at least $2D$. If you could somehow show that the set selected by the greedy algorithm has diameter $d \leq D$, then it would follow that its value is at most $\pi d \leq \pi D$.

share|cite|improve this answer
Thanks, will look at it. – The Unfun Cat Dec 11 '12 at 20:24

Your Answer


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.