Someone recently shared with me the following problem (which I guess appeared in some kind of past coding contest):
Given $n$ points $P_i=(x_i,y_i)$ in the 2-dimensional plane, find the point $Q=(x,y)$ that minimizes the average distance from $P_i$ to $Q$.
In other words, we want to find $Q$ that minimizes the objective function $f(Q) = \sum_i d(P_i,Q)$. Here $d(\cdot,\cdot)$ represents the usual Euclidean (L2) distance. I'm told that in the coding contest this was phrased in terms of finding the best location to put a washroom somewhere in an office building, so that the average distance to all employees is minimized.
Is there an elementary solution to this problem? In other words, a polynomial-time algorithm that does not require knowledge of advanced methods (say, beyond what undergraduate computer science majors could be expected to understand).
If we were on the 1D real line rather than the 2D plane, this problem would be easy. In one dimension, the solution is exactly the median of $x_1,\dots,x_n$. However, this does not seem to generalize to the 2-dimensional plane. It's tempting to take $x$ to be the median of $x_1,\dots,x_n$ and $y$ to be the median of $y_1,\dots,y_n$, but this does not provide the optimal solution: a counterexample is to look at three points at three of the corners of a square. (The component-wise median is at a corner, but the optimal location is somewhere inside the square.)
It looks like this problem is a special case of the two-dimensional Euclidean $p$-median problem, for $p=1$. Apparently the two-dimensional Euclidean $p$-median problem is NP-hard when $p$ is part of the input (Megiddo and Supowit, SIAM J Computing 13(1) Feb 1984) -- but here we have the special case where $p=1$, so the NP-hardness result doesn't apply to this special case. I haven't been able to use this search phrase to help find an algorithm.
If the distance metric was the Manhattan (L1) distance, there would be a number of clean solutions. The component-wise median would be optimal, since the Manhattan metric is linearly separable in the $x$-coordinates and $y$-coordinates. For similar reasons, we could solve it using linear programming. However, here we have the Euclidean distance, which is not linearly separable, so those methods do not seem to apply.
See also Find the point with minimum max distance to any point in a set, which looks at a related but different problem, the smallest-circle problem, where the objective function is $g(Q) = \max_i d(P_i,Q)$. However, the techniques used for that problem don't seem to apply here.
Right now the approach I can see is a heuristic algorithm: use standard black-box optimization methods such as hill-climbing or gradient ascent to find the point $Q$. However, there is no guarantee that this finds the exact optimum.
If there's a solution that does not require understanding advanced computational geometry algorithms (e.g., Voronoi diagrams, Delaunay triangulation, etc.), even better!
