Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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? –  JavaMan Oct 23 '11 at 22:04
    
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. –  Laciel Oct 23 '11 at 22:18

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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