3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\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.