An Approximation Algorithm for the Continuous k-Medians Problem in a Convex Polygon

We give a fast and simple factor 2.74 approximation algorithm for the problem of choosing the k medians of the continuum of demand points defined by a convex polygon C. Our algorithm first surrounds the input region with a bounding box, then subdivides the bounding box into subregions with equal area. Simulation results on the convex hulls of the 50 states in the United States show that the practical performance of our algorithm is within 10% of the optimal solution in the vast majority of cases.