patternMinor
Show that approximation ratio for a convex hull algorithm is $\pi/2$
Viewed 0 times
convexshowapproximationhullalgorithmthatforratio
Problem
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.
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.
Solution
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$.
Context
StackExchange Computer Science Q#7333, answer score: 3
Revisions (0)
No revisions yet.