Sensitivity of geometric median to moving one point

Question

The geometric median of a finite set $S$ of points in the Euclidean plane is defined as the point $m$ for which $\sum_{s\in S} d(m,s)$ is minimized, where $d(x,y)$ is the Euclidean distance between $x$ and $y$. As long as $S$ is not colinear, the geometric median is unique.

My question is this; if you replace a point $s\in S$ with some $s'$ for which $d(s,s')<\epsilon$, will the geometric median of the new set be at most $\epsilon$ away from the geometric median of the original?

The reason I want to know is that I could use this result in order to solve the puzzle here: Algorithm for people to congregate with limited relative location information.

I have verified this is true when $|S|=3$ and $|S|=4$, where the geometric median can be described explicitly. For example, when $S$ is the set of vertices of a convex quadrilateral, it can be shown the median of $S$ is the intersection of the diagonals. This intersection moves by less than $\epsilon$ when any vertex moves by $\epsilon$.

Answer 1

False. Let $S = \{(-2,0),(-1,1/4),(1,0),(2,0)\}$. Then $m = (1,0)$ (via mathematica, or by showing $(1,0)$ is a local minimum by analyzing small perturbations). Let $s = (1,0)$ and $s' = (1,1/4)$. Now, by symmetry and uniqueness of median, the new median, $m'$, has $x$-coordinate $0$. So $|m-m'| \ge 1$.

Answer 2

Yes, this statement must be true, and probably under looser conditions than you grant. Suppose we generalize to a unique median position $m_\alpha$ which minimizes the sum of the distances when the distances from $m_\alpha$ to all of the $s$ that are not moving are weighted by $\alpha$ in the sum. Then, $m_1 = m$. Moreover, $m_0$ is clearly just equal to the value of the moving $s$. That means that for $\alpha=0$ the distance this reweighted median travels is just the distance the moving point travels, $d(s,s')$. Because our result should be path independent, we choose the geodesic path from $s$ to $s'$.

Now suppose we calculate how fast $m_\alpha$ is changing as we increase $\alpha$. Intuitively, this extra function dilutes the effect of the one moving point $s$ so it can only decrease the distance the weighted median travels. This is true at every point in the trajectory of $s$ and for every $0 \le \alpha \le 1$ so the total distance the median travels keeps decreasing as $\alpha$ increases. Thus, we conclude that the total distance must be strictly less than $d(s,s')$.

For a more explicit demonstration of this "intuitive" property, consider a coordinate $x_\alpha$ that is the unique minimum of

$$f(x,\beta)+\alpha g(x)$$

so that

$$\partial_x f + \alpha \partial_x g = 0$$.

This above expression is evaluated at some $x_\alpha(\beta)$ so now let's differentiate both sides with respect to $\beta$, yielding:

$$(\partial_x^2 f +\alpha \partial_x^2 g) (\partial x/\partial \beta) + \partial_x \partial_\beta f = 0$$.

Here, then, the fact that $x_\alpha(\beta)$ is a unique minimum means that both terms in the initial parentheses must be positive. Hence, increasing $\alpha$ must decrease $\partial x/\partial \beta$ and we conclude that the total distance traveled, $\int d \beta (\partial x/\partial \beta)$ must also diminish at $\alpha$ increases.