A Metric Circuity Question:        Torsten Sillke, 26. Apr. 1996
                                   --- update  3. May. ---
Let d(.,.) be the distance function of a metric space,
and p > 1 (a circuity factor).

Given for points A, B, C, and D.

I want to compare d(A,D) with d(A,B) + d(B,C) + d(C,D).

Some restrictions on the four point:
I)    d(A,B) + d(B,D) <= p * d(A,D)
II)   d(A,C) + d(C,D) <= p * d(A,D)
III)  d(A,B) + d(B,C) <= p * d(A,C)
IV)   d(B,C) + d(C,D) <= p * d(B,D)

First let me consider only some circuity conditions.

If I) and II) then
  d(A,B) + d(B,C) + d(C,D) <= (2*p+1) * d(A,D)
  -- this is sharp. --

If III) and IV) then d(A,B) + d(B,C) + d(C,D) can be
arbitrarily large compared to d(A,D) even for p=1.
  Example: set B=C.

If I) and IV) [or II) and III)] then
  d(A,B) + d(B,C) + d(C,D) <= p*p * d(A,D)
  -- this is sharp. --

In the following I consider all four circuity conditions.
----------------------------------------------------------------
If I), II), III), and IV) then

  d(A,B) + d(B,C) + d(C,D) <= min(p*(3p-1)/(p+1), 2p+1) * d(A,D)
----------------------------------------------------------------

The two bounds meet at p0 = 2+sqrt(5). For p>=p0 this is
sharp, as every norm fits the bound.
Example in 1-dim: A = -1, B = p, C = -p, D = 1.
For p<=p0 this is sharp for distances on the sphere.

Analysis of p <= p0:
The problem can be stated as a LP-problem for fixed p.
Let d(A,D) = 1, one has to maximize f = d(A,B) + d(B,C) + d(C,D).
The constraints are: positivity, triangle-inequalities and
the circuity-inequalities I, II, III, and IV.
As the LP-problem is symmetric, each set of distances which meet
the constraints can be symmetrized having the same f.
Therefore we have only three parameters to determine.
Let x = d(A,B) = d(C,D),
    y = d(B,C),
    z = d(A,C) = d(B,D).
The LP-problem is:
    x >= 0
    y >= 0
    z >= 0
    x + y >= z
    x + z >= y
    y + z >= x
    x + z >= 1
    x + 1 >= z
    z + 1 >= x
    x + z <= p        (circuity condition)
    x + y <= p*z      (circuity condition)

    Maximize: 2*x+z

Solution of the LP-problem.
If p <= 2 + sqrt(5) the two circuity conditions will be equalities at
the maximal point. The optimal point is unique.
    x = p*(p-1)/(p+1)
    y = p
    z = 2*p/(p+1)

    2*x+z = p*(3*p-1)/(p+1)

----------------------------------------------------------------
Some special values of p (calculated for selected distances):

sprute@Mathematik.Uni-Bielefeld.DE (udo sprute) found good
extremal cases by a small c-program. (25. Apr 1996)

p = 1.5:  distance: 2-norm
          A  -0.5        0
          B  -0.599745  +0.335664
          C  +0.599745  -0.335664
          D  +0.5        0
          Quotient = 2.07491 = (d(A,B) + d(B,C) + d(C,D))/d(A,D)

p = 2:    distance: 2-norm
          A  -0.5        0
          B  -0.54356    0.726916
          C   0.54356   -0.726916
          D   0.5        0
          Quotient = 3.27178

p = 1.5:  distance: norm = max( 0.9 * 1-norm, oo-norm )
          A -0.5           0
          B -0.538076+eps  0.295257+eps
          C  0.538076-eps -0.295257-eps
          D  0.5           0
          Quotient = 2.1       (meets upper bound)

p = 2:    distance: norm = max( 2/3 * 1-norm, oo-norm )
          A -0.5       0
          B -0.833333 -0.666667
          C  0.833333  0.666667
          D  0.5       0
          Quotient = 3.33333   (meets upper bound)

p = 3:    distance: oo-norm
          A -0.5       0
          B -0.5       1.5
          C  0.5      -1.5
          D  0.5       0
          Quotient = 6         (meets upper bound)

p = 1.5:  distance on the sphere  (latitude, longitude in degree)
          A -60Deg     0
          B -90Deg   -20.9051574479Deg
          C  90Deg    20.9051574479Deg
          D  60Deg     0
          Quotient = 2.1       (meets upper bound)

p = 2:    distance on the sphere  (latitude, longitude in degree)
          A -45Deg   0
          B -90Deg  45Deg
          C  90Deg -45Deg
          D  45Deg   0
          Quotient = 3.33333   (meets upper bound)

p = 3:    distance on the sphere  (latitude, longitude in degree)
          A -30Deg   0
          B   0  -90Deg
          C   0   90Deg
          D  30Deg   0
          Quotient = 6         (meets upper bound)

----------------------------------------------------------------

Best bounds for the 1-norm (in 2 dim):     (27. Apr. 96)

  A = (-1, 0)
  B = ( g, p-1 )
  C = (-g,-p+1 )
  D = ( 1, 0)

            /    1               if p >= 2 + sqrt(5) = 4.2360679
  with g =  |  (p-1)(p-2)/(p+3)  if 2 <= p <= 2 + sqrt(5)
            \    0               if 1 <= p <= 2

  d(A,D) = 2
  d(A,B) + d(B,C) + d(C,D) = 4p + 4g - 2
  quotient = 2p + 2g - 1
  The upper bound 2p+1 is reached for p >= 2 + sqrt(5).

Best bounds for the oo-norm (in 2 dim):   (28. Apr. 96)

  This case gives better bounds than the 1-norm one. But it
  reaches the upper bound 2p+1 at the same value.

Best bounds for distances (arclength) on the sphere:  (2. May 96)

  For p <= 2 + sqrt(5) you get the metric bound.

  d(A,B) = d(C,D) = 180Deg * (p-1)/(p+1)
  d(A,D) = 180Deg / p
  d(B,C) = 180Deg
  d(A,C) = d(B,D) = 360Deg / (p+1)

  A = (-90Deg/p, 0)
  B = (-90Deg,   arccos( cos(d(AB)) / sin(d(AD)/2) )
  C = ( 90Deg,  -arccos( cos(d(AB)) / sin(d(AD)/2) )
  D = ( 90Deg/p, 0)

  If p>3 the latitude is bigger than 90Deg. Therefore B and C are swapped.

----------------------------------------------------------------

Generalized Problem:
  Let X1, X2, ..., Xn be Points of a metric space, such that for
  each i<j<k: d(Xi,Xj) + d(Xj,Xk) <= p * d(Xi,Xk) holds.
  What is the maximal value of

  (d(X1,X2) + d(X2,X3) + ... + d(X(n-1),Xn)) / d(X1,Xn).

Limit Case:
  For n->oo, what is the limit curve for the problem stated above
  for euclidian distance in R*R?