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.

Assume that we have a metric space $(S,d)$ and points $a,b,c \in S$ which statisfy the following conditions:

  • for all $x \in S$, $d(a,x) \leq d(a,b)$,
  • for all $y\in S$, $d(b,y) \leq d(b,c)$.

Does the following statement follow from these two assumptions?

  • for all $x,y\in S$, $d(x,y) \leq d(b,c)$

In words: if $b$ is a furthest point from $a$ and $c$ is a furthest point from $b$, is $d(b,c)$ the maximum possible distance between points in $S$?


In case someone is interested in the motivation: I was trying to see how much graph structure is needed in the proof that using two BFSes we can find the diameter of a finite connected graph:

  1. Start from $a$ and find a vertex $b$ with maximum distance from $a$.
  2. Start from $b$ and find a vertex $c$ with maximum distance from $b$.
  3. $d(b,c)$ is the diameter of the graph.

The algorithm doesn't work correctly. Here is a counterexample:

enter image description here

share|improve this question
    
+1 Nice question, Kaveh. –  Babak S. Mar 23 '13 at 6:09

2 Answers 2

up vote 2 down vote accepted

In the plane let $a=c=\langle -1,0\rangle$, $b=\langle 1,0\rangle$, $x=\langle 0,z\rangle$, and $y=\langle 0,-z\rangle$, and let $S=\{a,b,x,y\}$. If $1<z<\sqrt3$, then $b$ is maximally far from $a$, $c$ is maximally far from $b$, and $d(x,y)>2=d(b,c)$.

share|improve this answer
    
what would be the best bound then? –  Mathematician Mar 23 '13 at 5:56
    
@Mathematician: Off the top of my head I see nothing better than the obvious one given by the triangle inequality: $$d(x,y)\le d(x,b)+d(b,y)\le 2d(b,c)\;.$$ –  Brian M. Scott Mar 23 '13 at 5:59
    
Thanks Brian for the example. ps: is it possible to have an example where the distances are all natural numbers? (or do you think it is better to ask a new question?) –  Kaveh Mar 23 '13 at 6:04
    
@Kaveh: You’re welcome. –  Brian M. Scott Mar 23 '13 at 6:07

Take the set of points to be the intersection of the following two circles in $R^2$ and the metric to the normal euclidean distance metric,

$x^2+y^2=1,(x-1)^2+y^2=(3/2)^2$

Take $a=(0,0),b=(1,0),c=(-1/2,0)$

These satisfy the conditions in the problem,

Now take the points of intersection of both the circles, these are $(-1/8,3\sqrt{7}/8),(-1/8,-3\sqrt{7}/8)$. The distance between these two point is $3\sqrt{7}/4$

$7>4\Rightarrow 3\sqrt{7}/4>3/2=d(b,c)$.

So we have a contradiction.

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.