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.
A: 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, May-June 2000, pp. 444-460.
"The Multi-Source Weber Problem with Constant Opening Cost,"
Journal of Operations Research Society, 2004, 55, 640-6.
A: There's no particular range of $k$ that I'm interested in; actually, I'm just curious if there's already a well-known 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.
