Q:

Algorithm for k-medians in a convex polygon

Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon?  That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a convex polygon $C$ so as to minimize $$\iint_C \min_i \|x-p_i\| dx$$

A:

The problem you're asking about (for $k=1$) is called the continuous Fermat-Weber problem. The primary work on this that I'm aware of is the 2003 paper by Fekete, Mitchell and Beurer. While they examine this problem, they focus on the $\ell_1$ plane (the analytics are easier) and also pay more attention to the $k=1$ case, while also discussing some hardness results. 
My $.02$ is that there should be some way of getting an approximation by discretizing the region - it's not clear to me that convexity helps a lot though. 

A:

A while ago I wrote, but never published, an approximation algorithm for this problem.  Using some new results and updating the citations, it looks like I can get the approximation constant down to 9.026 (assuming I didn't make any mistakes).  It's not clear to me if that's publication-worthy, but I uploaded a draft to
http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf
if anyone is interested.

