1

Let $X\subset \mathbb R^3$ be finite, and $y$ be a point of $\mathbb R^3\backslash X$. Let $x_0$ be a point of $X$ such that there is no other point of $X$ closer to $y$ than $x_0$.

I want to show that for all $x'\in X\backslash\{x_0\}$, $d(\tilde x,x')>d(\tilde x,x_0)$, with $\tilde x := \frac{y+x_0}{2}$. (And thus there is a ball arounfd $y$ containing $x_0$ and no other point of $X$).

This seems fairly intuitive and simple, but after playing around with triangle inequalities for a while I got nothing. Here is one of my attempts:

Suppose $d(\tilde x,x')\le d(\tilde x,x_0)$. Then: $$ d(y,x')\le d(y,\tilde x) + d(\tilde x, x') \le \frac{1}{2}d(y,x_0) + d(\tilde x,x') = d(y,x_0) $$ Since we cannot have $d(y,x')<d(y,x_0)$, then $d(y,x')=d(y,x_0)$ So far, so good. But now I am not managing to get a contradiction. I have been trying to show that this implies $x_0=x'$ using triangle inequalities, but with no success.

soap
  • 2,694

2 Answers2

1

With $r=d(y,x_0)$, we have $d(\tilde x,y)=d(\tilde x,x_0)=\frac 12r$. The ball $B(\frac12r, \tilde x)$ of radius $\frac 12r$ around $\tilde x$ is a subset of the ball $B(r,y)$ of radius $r$ around $y$ because $d(x,\tilde x)<\frac12r$ implies $$d(x,y)\le d(x,\tilde x)+d(\tilde x,y)<\frac 12r+\frac 12r=r.$$ The same argument works for the closed balls (i.e., with $\le$ in place of $<$). for all points $x'\ne x$ in $X$, we know that $d(x',y)\ge r$.

However, using the properties of metrics alone, we cannot show that $d(x',\tilde x)>\frac r2$. We need to use specific properties of our used (i.e., the Euclidean) metric. Indeed, with a different metric (e.g., the so-called Manhattan or taxi-cab metric $d(\langle x_1,x_2\rangle, \langle y_1,y_2\rangle:=\max\{|x_1-y_1|,|x_2-y_2|\}$) the desired result may be downright false. In fact, with a general metric, it need not even be the case that $\frac{x_0+y}2$ is a point "halfway between" $x_0$ and $y$, distance-wise. So what are the special property of the Euclidean metric that we need?

  1. The euclidean metric is induced by a norm (the euclidean norm). Therefore $\tilde x=\frac{x_0+y}2$ implies $d(x_0,y)=\|y-x_0\|=2\|\frac{y-x_0}2\|=2\|y-\tilde x=2d(\tilde x,y)$ and similarly $=2d(\tilde x,x_0)$. (This is also true for the Manhatten distance, so apparently we need a second property)

  2. We know when the triangle inequality is sharp, i.e., we can make the more precise statement $$ d(x,z)\le d(x,y)+d(y,z)$$ with equality if and only if $x,y,z$ are collinear and $y$ is on the straight line segment with endpoints $x$ and $z$

Now back to the original problem: Suppose $x'\in X$ and $x'\ne x_0$. Then $$\tag1r\stackrel {\alpha}\le d(x',y) \stackrel {\beta}\le d(x',\tilde x)+d(\tilde x,y)=d(x',\tilde x)+\frac r2.$$ and form this $d(x',\tilde x)\ge\frac r2$. The only way to have $x'\in \overline B(\frac r2,\tilde x)$ is therefore if both inequalities in $(1)$ are in fact equalities. For inequality $\alpha$, this means that $d(x',y)=r$ and for $\beta$ it means (among others) that $x_0,y,x'$ are collinear. A closer look reveals that these conditions together imply that either $x'=x_0$ (which we excluded) or $y$ is the midpoint of $x_0$ and $x'$ (in which case we explicitly compute $d(\tilde x,x')=\frac32r>\frac12r$).

Hagen von Eitzen
  • 374,180
  • It seems to me that $\beta$ implies that $\tilde x, y, x'$ are collinear, not $,y, x_0$. What am I missing? I am simply applying the sharpness property here. – soap Mar 04 '19 at 17:11
1

If metric $d$ is defined by $d(x,y)=||x-y||=\sqrt{(x_{1}-y_1)^{2}+(x_{2}-y_2)^{2}+(x_{3}-y_3)^{2}}$ then first solve the problem for special case $x=(0,0,0)$ and $(2,0,0)\in X\subseteq\{y\in\mathbb R^3\mid ||y||\geq 2\}$.

It is evident that the ball $B$ with center $(1,0,0)$ and radius $1$ will satisfy $B\cap X=\{(2,0,0)\}$ and $(0,0,0)\in B$.

This can easily made more general by translations, rotations etc.

If the metric is not defined like that then it is not certain that it is true.

For instance if we take $d(x,y)=\max(|x_1-y_1|,|x_2-y_2|,|x_3-y_3|)$ then it is not true.

drhab
  • 151,093