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.
Show that approximation ratio for a convex hull algorithm is $\pi/2$
algorithms;approximation;greedy algorithms