6
$\begingroup$

How can I show that the Euclidean distance satisfies the triangle inequality?

Where the Euclidean distance is given by: $$d(p,q) = \sqrt{(p_1-q_1)^2 + \cdots + (p_n-q_n)^2}$$

Triangle Inequality: $\forall x,y,z\Bigl( d(x,z) \leq d(x,y) + d(y,z)\Bigr)$.

  • 5
    This is your third question on the same topic in just over one hour. Instead of asking questions here, why don't you take some time and try this questions yourself? If you have in fact tried these questions by yourself, where did you find difficulty?2011-10-23
  • 1
    I have tried these questions before asking. For this question. I used the case where (x - z)^2 ≤ (sqrt(x - y)^2 + sqrt(y - z)^2)^2. But I am not sure where to go from there.2011-10-23

1 Answers 1

13

Let ${\bf p} = (p_1,\dots,p_n)$ and ${\bf q}=(q_1,\dots,q_n)$. Recall that ${\bf p \cdot q} = p_1q_1 + \cdots + p_nq_n$ and $|{\bf p}|=\sqrt{{\bf p \cdot p}}$ and finally $d({\bf p}, {\bf q})=|{\bf p}-{\bf q}|$.

First, let's establish the Cauchy-Schwarz inequality: $|{\bf p \cdot q}| \leq |{\bf p}| |{\bf q}|$.

Consider $|{\bf p}-c{\bf q}|^2 = ({\bf p}-c{\bf q}) {\bf \cdot} ({\bf p}-c{\bf q}) = c^2 {\bf q \cdot q} - 2c {\bf p \cdot q} + {\bf p \cdot p}=|{\bf q}|^2c^2-2({\bf p\cdot q})c+|{\bf p}|^2$.

This is a quadratic in $c$ and since $|{\bf p}-c{\bf q}|^2 \geq 0$ we have $|{\bf q}|^2c^2-2({\bf p\cdot q})c+|{\bf p}|^2 \geq 0$. Thus this quadratic either has a repeated real root or complex roots. Thus its discriminant is non-positive. So $(-2({\bf p \cdot q}))^2-4|{\bf q}|^2|{\bf p}|^2 \leq 0$. This means $4({\bf p\cdot q})^2 \leq 4|{\bf q}|^2|{\bf p}|^2$. Canceling the 4's and taking square roots give us the required result.

Use Cauchy-Schwarz as follows: $|{\bf p}+{\bf q}|^2=({\bf p}+{\bf q}){\bf \cdot}({\bf p}+{\bf q})=|{\bf p}|^2+2({\bf p\cdot q})+|{\bf q}|^2 \leq |{\bf p}|^2+2|{\bf p\cdot q}|+|{\bf q}|^2$ $\leq |{\bf p}|^2+2|{\bf p}||{\bf q}|+|{\bf q}|^2=(|{\bf p}|+|{\bf q}|)^2$. This gives you $|{\bf p}+{\bf q}| \leq |{\bf p}|+|{\bf q}|$.

Now consider 3 points ${\bf p}$, ${\bf q}$, and ${\bf r}$. $d({\bf p}, {\bf r})=|{\bf p}-{\bf r}|=|{\bf p}-{\bf q}+{\bf q}-{\bf r}| \leq |{\bf p}-{\bf q}| + |{\bf q}-{\bf r}|=d({\bf p},{\bf q})+d({\bf q},{\bf r})$