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$
  • 1
    $\begingroup$ Perhaps they meant distance squared? The answer is then just the average of all points. $\endgroup$ – Yuval Filmus Oct 3 '14 at 0:40
  • $\begingroup$ @YuvalFilmus, ahh, good observation! That would certainly make the problem far easier. Thank you. $\endgroup$ – D.W. Oct 3 '14 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$ – user3483902 Oct 3 '14 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$ – user3483902 Oct 5 '14 at 22:07
6
$\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, privacy policy and cookie policy

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