Are there any known approximation algorithms or exact solution schemes for the kmedians 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 \xp_i\ dx$$

The problem you're asking about (for $k=1$) is called the continuous FermatWeber 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 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 publicationworthy, but I uploaded a draft to http://www.tc.umn.edu/~jcarlsso/fermatweber.pdf if anyone is interested. 


Following Suresh's lead, this problem is known as the multisource Weber problem, and searching that key phrase turns up several papers in the operations research literature. For example: "Improvement and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem," Operations Research, Vol. 48, No. 3, MayJune 2000, pp. 444460. "The MultiSource Weber Problem with Constant Opening Cost," Journal of Operations Research Society, 2004, 55, 6406. 


There's no particular range of $k$ that I'm interested in; actually, I'm just curious if there's already a wellknown PTAS or an approximation algorithm, and whether that's considered an "interesting" problem in the geometry community. It seems that the problem becomes easier as $k$ becomes really big, since you just want to scatter the points in as uniform a fashion as possible (like the centers of a hexagonal tiling or something like that). EDIT: Sorry folks, looks like I replied in the wrong place. 

