5
$\begingroup$

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!

$\endgroup$
4
  • 1
    $\begingroup$ Perhaps they meant distance squared? The answer is then just the average of all points. $\endgroup$ Oct 3, 2014 at 0:40
  • $\begingroup$ @YuvalFilmus, ahh, good observation! That would certainly make the problem far easier. Thank you. $\endgroup$
    – D.W.
    Oct 3, 2014 at 0:41
  • $\begingroup$ Are there any randomized algorithms for the same problem that give optimal answers for the distance square, (that would be the L2 norm?)- did not want another question, as the question asked above was very clear! $\endgroup$ Oct 3, 2014 at 18:56
  • $\begingroup$ Would this greedy approach work, have a delauney triangulation of the whole set of points, and then find the centroids of each of the triangles. Then repeat the process, ie, triangulate the centroids, and find the centroid, repeat until we have only one centroid. The centroid gives the average of all the points in the shape. As there are points, we need to get shapes from them to reason about the points, so triangulation. A centroid returns the average of all the points in the space, and so on. $\endgroup$ Oct 5, 2014 at 22:07

1 Answer 1

7
$\begingroup$

This point is known as the geometric median, also known as the 1-median.

Apparently, there is no simple algorithm for computing the geometric median. Instead, one must use some kind of numerical approximation. Wikipedia mentions Weiszfeld's algorithm, which appears to be a kind of iterative descent algorithm, and cites other more sophisticated algorithms.

This is a special case of the Weber problem, a facility location problem. Standard solvers for facilitation location problems be able to compute the geometric median for you, by framing this as an instance of the Weber problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.