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$$

1$\begingroup$ Nice question! For the ellipse $x^2/a^2 + y^2/b^2 = 1$ and $k=2$, the points are not at the foci. For $a=2$, $b=1$, about $(\pm 0.85,0)$. $\endgroup$ – Joseph O'Rourke Dec 21 '10 at 0:52

$\begingroup$ Is there even a nice algorithm for k=1 ? $\endgroup$ – HenrikRüping Dec 21 '10 at 14:00

$\begingroup$ @Henrik: Good question! Not generally at the center of gravity... $\endgroup$ – Joseph O'Rourke Dec 21 '10 at 19:32

1$\begingroup$ For $k=1$, the functional is convex and, if you have any way to compute it in a reasonable time (say, by partitioning into triangles, or so), you can use the standard gradient descent methods. All that fails miserably for larger $k$. The minimum is no longer unique (say for 2 points in an equilateral triangle) and everything becomes a mess. What range of $k$ are you interested in? $\endgroup$ – fedja Dec 22 '10 at 0:18

$\begingroup$ @Joseph: If you square the distance and $k=1$, then it's the center of gravity. $\endgroup$ – Michael Hardy Dec 22 '10 at 22:30
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.

$\begingroup$ Why? I agree that when the function is just barely convex, you may have headaches with the descent methods but this one has a good a priori bound for the second derivative in every direction, so the most naiive implementations require just logarithm of the precision steps. $\endgroup$ – fedja Dec 22 '10 at 18:58

$\begingroup$ I was referring to convexity in the region, not the function. $\endgroup$ – Suresh Venkat Dec 23 '10 at 17:21
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.

$\begingroup$ that is interesting ! thanks for sharing the draft. $\endgroup$ – Suresh Venkat Dec 26 '10 at 9:03

$\begingroup$ Thanks, I already caught and fixed two typos since posting. $\endgroup$ – John Gunnar Carlsson Dec 26 '10 at 20:50

$\begingroup$ Update: brought the approximation constant down to 5.02. $\endgroup$ – John Gunnar Carlsson Jan 3 '11 at 7:25

$\begingroup$ The link in your answer seems to be dead. Is the new link supposed to be this one: wwwbcf.usc.edu/~jcarlsso/fermatweber.pdf (Wayback Machine) $\endgroup$ – Martin Sleziak Mar 6 '19 at 12:52
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.

$\begingroup$ juat a clarification though: it seems to me that both links still refer to the discrete setting (i.e the kmedian) where the number of "users" is finite. Aside: I didn't know that there's this entire subfield devoted to the kmedian under this name. certainly the theoryCS literature doesn't directly mention it, and the OR community appears to return the favor :) $\endgroup$ – Suresh Venkat Dec 25 '10 at 17:58

$\begingroup$ @Suresh: Yes, you are right, these references are to the discrete version. And it is quite interesting that the two communities are apparently unaware of one another! Maybe this MO question will serve as a start toward bridging that gap. $\endgroup$ – Joseph O'Rourke Dec 25 '10 at 18:41
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.

$\begingroup$ The problem seems to be that you haven't registered yet so you have multiple accounts floating around. Once you've registered, post in this meta thread to ask the moderators to merge your accounts tea.mathoverflow.net/discussion/605/mergetwouserids/#Item_0 $\endgroup$ – j.c. Dec 25 '10 at 23:49