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.