HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Show that approximation ratio for a convex hull algorithm is $\pi/2$

Submitted by: @import:stackexchange-cs··
0
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.

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.