10
$\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)$.

$\endgroup$
19
$\begingroup$

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})$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please explain the line "Thus this quadratic either has a repeated real root or complex roots." It is not obvious to me. $\endgroup$ – R_D Aug 29 at 4:53
  • $\begingroup$ $0 \leq |p-cq|^2 = Ac^2+Bc+C$ where $A,B,C$ are the numbers $A=|q|^2$, $B=-2p.q$, and $C=|p|^2$. Notice we have a quadratic $Ax^2+Bx+C \geq 0$ here. So if you draw the graph of $y=Ax^2+Bx+C$, the parabola can at most bounce off of the $x$-axis (if =0) and otherwise is strictly above the $x$-axis (where >0). Such a quadratic cannot have distinct real roots. If it hits 0 at one point, it must have a repeated real root. If it never hits 0, it must have complex roots. These two cases occur (remembering the quadratic formula) when $B^2-4AC \leq 0$ $\endgroup$ – Bill Cook Aug 29 at 14:17

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.