Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
    
Thanks, will look at it. –  The Unfun Cat Dec 11 '12 at 20:24
add comment

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.