Tight span

<h2 id="definition">Definition</h2>
The tight span of a metric space can be defined as follows. Let (X,d) be a metric space, and let T(X) be the set of extremal functions on X, where we say an extremal function on X to mean a function f from X to R such that

<ol><li>For any x, y in X, d(x,y) ≤ f(x) + f(y), and</li>
<li>For each x in X, f(x) = sup{d(x,y) - f(y):y in X}.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>: 124 </li></ol>
In particular (taking x = y in property 1 above) f(x) ≥ 0 for all x. One way to interpret the first requirement above is that f defines a set of possible distances from some new point to the points in X that must satisfy the <a href="/facts/Triangle_inequality/KubLjkwr">triangle inequality</a> together with the distances in (X,d). The second requirement states that none of these distances can be reduced without violating the triangle inequality.
The tight span of (X,d) is the metric space (T(X),δ), where

δ
        =
        (
        inf
        {
        C
        ∈
        
          
            R
          
          
            ≥
            0
          
        
        :
        
          |
        
        g
        (
        x
        )
        −
        f
        (
        x
        )
        
          |
        
        ≤
        C
        
           for all 
        
        x
        ∈
        X
        }
        
          )
          
            f
            ,
            g
            ∈
            T
            (
            X
            )
          
        
        =
        (
        ‖
        g
        −
        f
        
          ‖
          
            ∞
          
        
        
          )
          
            f
            ,
            g
            ∈
            T
            (
            X
            )
          
        
      
    
    {\displaystyle \delta =(\inf\{C\in \mathbb {R} _{\geq 0}:|g(x)-f(x)|\leq C{\text{ for all }}x\in X\})_{f,g\in T(X)}=(\|g-f\|_{\infty })_{f,g\in T(X)}}

is analogous to the metric induced by the <a href="/facts/Lp_space/gbad0Rv1">ℓ∞ norm</a>. (If d is bounded, then δ is the subspace metric induced by the metric induced by the <a href="/facts/Lp_space/gbad0Rv1">ℓ∞ norm</a>. If d is not bounded, then every extremal function on X is unbounded and so 
 
 
 
 T
 (
 X
 )
 ⊈
 
 ℓ
 
 ∞
 
 
 (
 X
 )
 .
 
 
 {\displaystyle T(X)\not \subseteq \ell ^{\infty }(X).}
 
 Regardless, it will be true that for any f,g in T(X), the difference 
 
 
 
 g
 −
 f
 
 
 {\displaystyle g-f}
 
 belongs to 
 
 
 
 
 ℓ
 
 ∞
 
 
 (
 X
 )
 
 
 {\displaystyle \ell ^{\infty }(X)}
 
, i.e., is bounded.)

<h2 id="equivalent-definitions-of-extremal-functions">Equivalent definitions of extremal functions</h2>
For a function f from X to R satisfying the first requirement, the following versions of the second requirement are equivalent:

<ul><li>For each x in X, f(x) = sup{d(x,y) - f(y):y in X}.</li>
<li>f is pointwise minimal with respect to the aforementioned first requirement, i.e., for any function g from X to R such that d(x,y) ≤ g(x) + g(y) for all x,y in X, if g≤f pointwise, then f=g.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>: 93, Proposition 4.6.2 <a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>: Lemma 5.1 </li></ul>
<h2 id="basic-properties-and-examples">Basic properties and examples</h2>
<ul><li>For all x in X, 
 
 
 
 0
 ≤
 f
 (
 x
 )
 .
 
 
 {\displaystyle 0\leq f(x).}
 
</li>
<li>For each x in X, 
 
 
 
 (
 d
 (
 x
 ,
 y
 )
 
 )
 
 y
 ∈
 X
 
 
 
 
 {\displaystyle (d(x,y))_{y\in X}}
 
 is extremal. (Proof: Use symmetry and the <a href="/facts/Triangle_inequality/KubLjkwr">triangle inequality</a>.)<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>If X is finite, then for any function f from X to R that satisfies the first requirement, the second requirement is equivalent to the condition that for each x in X, there exists y in X such that f(x) + f(y) = d(x,y). (If 
 
 
 
 X
 =
 ∅
 ,
 
 
 {\displaystyle X=\emptyset ,}
 
 then both conditions are true. If 
 
 
 
 X
 ≠
 ∅
 ,
 
 
 {\displaystyle X\neq \emptyset ,}
 
 then the supremum is achieved, and the first requirement implies the equivalence.)</li>
<li>Say |X|=2, and choose distinct a, b such that X={a,b}. Then 
 
 
 
 T
 (
 X
 )
 =
 {
 f
 ∈
 (
 
 
 R
 
 
 ≥
 0
 
 
 
 )
 
 X
 
 
 :
 f
 (
 a
 )
 +
 f
 (
 b
 )
 =
 d
 (
 a
 ,
 b
 )
 }
 
 
 {\displaystyle T(X)=\{f\in (\mathbb {R} _{\geq 0})^{X}:f(a)+f(b)=d(a,b)\}}
 
 is the convex hull of {{(a,1),(b,0)},{(a,0),(b,1)}}. [Add a picture. Caption: If X={0,1}, then 
 
 
 
 T
 (
 X
 )
 =
 {
 v
 ∈
 (
 
 
 R
 
 
 ≥
 0
 
 
 
 )
 
 2
 
 
 :
 
 v
 
 0
 
 
 +
 
 v
 
 1
 
 
 =
 d
 (
 0
 ,
 1
 )
 }
 
 
 {\displaystyle T(X)=\{v\in (\mathbb {R} _{\geq 0})^{2}:v_{0}+v_{1}=d(0,1)\}}
 
 is the convex hull of {(0,1),(1,0)}.]<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>: 124 </li>
<li>Every extremal function f on X is Katetov:<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>: Section 2  f satisfies the first requirement and 
 
 
 
 ∀
 x
 ,
 y
 ∈
 X
 
 f
 (
 x
 )
 ≤
 d
 (
 x
 ,
 y
 )
 +
 f
 (
 y
 )
 ,
 
 
 {\displaystyle \forall x,y\in X\quad f(x)\leq d(x,y)+f(y),}
 
 or equivalently, f satisfies the first requirement and 
 
 
 
 ∀
 x
 ,
 y
 ∈
 X
 
 
 |
 
 f
 (
 y
 )
 −
 f
 (
 x
 )
 
 |
 
 ≤
 d
 (
 x
 ,
 y
 )
 
 
 {\displaystyle \forall x,y\in X\quad |f(y)-f(x)|\leq d(x,y)}
 
 (is 1-<a href="/facts/Lipschitz_continuity/Hw20EPEU">Lipschitz</a>), or equivalently, f satisfies the first requirement and 
 
 
 
 ∀
 x
 ∈
 X
 
 sup
 {
 f
 (
 y
 )
 −
 d
 (
 x
 ,
 y
 )
 :
 y
 ∈
 X
 }
 =
 f
 (
 x
 )
 .
 
 
 {\displaystyle \forall x\in X\quad \sup\{f(y)-d(x,y):y\in X\}=f(x).}
 
<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>: Proof of Proposition 4.6.1 <a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>T(X)⊆<a href="/facts/Continuous_functions_on_a_compact_Hausdorff_space/v5Yf5tlM">C(X)</a>. (Lipschitz functions are continuous.)</li>
<li>T(X) is <a href="/facts/Equicontinuous/cKjFQWD6">equicontinuous</a>. (Follows from every extremal function on X being 1-Lipschitz; cf. <a href="/facts/Equicontinuity/cKjFQWD6">Equicontinuity#Examples</a>.)</li>
<li>Not every Katetov function on X is extremal. For example, let a, b be distinct, let X = {a,b}, let d = ([x≠y])x,y in X be the <a href="/facts/Discrete_metric/hpvXA23u">discrete metric</a> on X, and let f = {(a,1),(b,2)}. Then f is Katetov but not extremal. (It is almost immediate that f is Katetov. f is not extremal because it fails the property in the third bullet of this section.)</li>
<li>If d is bounded, then every f in T(X) is bounded. In fact, for every f in T(X), 
 
 
 
 ‖
 f
 
 ‖
 
 ∞
 
 
 ≤
 ‖
 d
 
 ‖
 
 ∞
 
 
 .
 
 
 {\displaystyle \|f\|_{\infty }\leq \|d\|_{\infty }.}
 
 (Note 
 
 
 
 d
 ∈
 
 ℓ
 
 ∞
 
 
 (
 X
 ×
 X
 )
 .
 
 
 {\displaystyle d\in \ell ^{\infty }(X\times X).}
 
) (Follows from the third equivalent property in the above section.)</li>
<li>If d is unbounded, then every f in T(X) is unbounded. (Follows from the first requirement.)</li>
<li>
 
 
 
 T
 (
 X
 )
 
 
 {\displaystyle T(X)}
 
 is closed under pointwise limits. For any pointwise convergent 
 
 
 
 f
 ∈
 (
 T
 (
 X
 )
 
 )
 
 ω
 
 
 ,
 
 
 {\displaystyle f\in (T(X))^{\omega },}
 
 
 
 
 
 lim
 f
 ∈
 T
 (
 X
 )
 .
 
 
 {\displaystyle \lim f\in T(X).}
 
</li>
<li>If (X,d) is compact, then (T(X),δ) is compact.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>: Proposition 4.6.3  (Proof: The <a href="/facts/Extreme_value_theorem/eSV6P7eh">extreme-value theorem</a> implies that d, being continuous as a function 
 
 
 
 X
 ×
 X
 →
 
 R
 
 ,
 
 
 {\displaystyle X\times X\to \mathbb {R} ,}
 
 is bounded, so (see previous bullet) 
 
 
 
 T
 (
 X
 )
 ⊆
 {
 f
 ∈
 C
 (
 X
 )
 :
 ‖
 f
 
 ‖
 
 ∞
 
 
 ≤
 ‖
 d
 
 ‖
 
 ∞
 
 
 }
 
 
 {\displaystyle T(X)\subseteq \{f\in C(X):\|f\|_{\infty }\leq \|d\|_{\infty }\}}
 
 is a bounded subset of C(X). We have shown T(X) is equicontinuous, so the <a href="/facts/Arzel%C3%A0%E2%80%93Ascoli_theorem/eqSFHXbo">Arzelà–Ascoli theorem</a> implies that T(X) is <a href="/facts/Relatively_compact/z5uIqMDp">relatively compact</a>. However, the previous bullet implies T(X) is closed under the 
 
 
 
 
 ℓ
 
 ∞
 
 
 
 
 {\displaystyle \ell ^{\infty }}
 
 norm, since 
 
 
 
 
 ℓ
 
 ∞
 
 
 
 
 {\displaystyle \ell ^{\infty }}
 
 convergence implies pointwise convergence. Thus T(X) is compact.)</li>
<li>For any function g from X to R that satisfies the first requirement, there exists f in T(X) such that f≤g pointwise.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>: Lemma 4.4 </li>
<li>For any extremal function f on X, 
 
 
 
 ∀
 x
 ∈
 X
 
 f
 (
 x
 )
 =
 sup
 {
 
 |
 
 f
 (
 y
 )
 −
 d
 (
 x
 ,
 y
 )
 
 |
 
 :
 y
 ∈
 X
 }
 .
 
 
 {\displaystyle \forall x\in X\quad f(x)=\sup\{|f(y)-d(x,y)|:y\in X\}.}
 
<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>: Proposition 4.6.1 <a class="footnote-ref" id="fnref:16" href="#fn:16">16</a></li>
<li>For any f,g in T(X), the difference 
 
 
 
 g
 −
 f
 
 
 {\displaystyle g-f}
 
 belongs to 
 
 
 
 
 ℓ
 
 ∞
 
 
 (
 X
 )
 
 
 {\displaystyle \ell ^{\infty }(X)}
 
, i.e., is bounded. (Use the above bullet.)</li>
<li>The Kuratowski map<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>: 125  
 
 
 
 e
 :=
 (
 (
 d
 (
 x
 ,
 y
 )
 
 )
 
 y
 ∈
 X
 
 
 
 )
 
 x
 ∈
 X
 
 
 
 
 {\displaystyle e:=((d(x,y))_{y\in X})_{x\in X}}
 
 is an <a href="/facts/Isometry/K5wX8ah6">isometry</a>. (When X=∅, the result is obvious. When X≠∅, the <a href="/facts/Reverse_triangle_inequality/KubLjkwr">reverse triangle inequality</a> implies the result.)</li>
<li>Let f in T(X). For any a in X, if f(a)=0, then f=e(a).<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>: Lemma 5.1  (For every x in X we have 
 
 
 
 (
 e
 (
 a
 )
 )
 (
 x
 )
 =
 d
 (
 a
 ,
 x
 )
 ≤
 f
 (
 a
 )
 +
 f
 (
 x
 )
 =
 f
 (
 x
 )
 .
 
 
 {\displaystyle (e(a))(x)=d(a,x)\leq f(a)+f(x)=f(x).}
 
 From minimality (second equivalent characterization in above section) of f and the fact that 
 
 
 
 e
 (
 a
 )
 
 
 {\displaystyle e(a)}
 
 satisfies the first requirement it follows that 
 
 
 
 f
 =
 
 e
 
 a
 
 
 .
 
 
 {\displaystyle f=e_{a}.}
 
)</li>
<li>(X,d) is <a href="/facts/Hyperbolic_metric_space/Daqo6Ah2">hyperbolic</a> if and only if (T(X),δ) is hyperbolic.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>: Theorem 5.3 </li></ul>
<h2 id="hyperconvexity-properties">Hyperconvexity properties</h2>
<ul><li>(T(X),δ) and 
 
 
 
 
 (
 
 X
 ∪
 (
 T
 (
 X
 )
 ∖
 range
 ⁡
 e
 )
 ,
 
 δ
 
 (
 T
 (
 X
 )
 ∖
 range
 ⁡
 e
 )
 ×
 (
 T
 (
 X
 )
 ∖
 range
 ⁡
 e
 )
 
 
 ∪
 (
 δ
 (
 e
 (
 x
 )
 ,
 e
 (
 y
 )
 )
 
 )
 
 x
 ,
 y
 ∈
 X
 
 
 ∪
 (
 δ
 (
 e
 (
 x
 )
 ,
 g
 )
 
 )
 
 x
 ∈
 X
 ,
 g
 ∈
 T
 (
 X
 )
 ∖
 range
 ⁡
 e
 
 
 ∪
 (
 δ
 (
 f
 ,
 e
 (
 y
 )
 
 )
 
 f
 ∈
 T
 (
 X
 )
 ∖
 range
 ⁡
 e
 ,
 y
 ∈
 X
 
 
 
 )
 
 
 
 {\displaystyle \left(X\cup (T(X)\setminus \operatorname {range} e),\delta _{(T(X)\setminus \operatorname {range} e)\times (T(X)\setminus \operatorname {range} e)}\cup (\delta (e(x),e(y)))_{x,y\in X}\cup (\delta (e(x),g))_{x\in X,g\in T(X)\setminus \operatorname {range} e}\cup (\delta (f,e(y))_{f\in T(X)\setminus \operatorname {range} e,y\in X}\right)}
 
 are both <a href="/facts/Injective_metric_space/kExQ3lST">hyperconvex</a>.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>: Proposition 4.7.1 </li>
<li>For any Y such that 
 
 
 
 range
 ⁡
 e
 ⊆
 Y
 ⊊
 X
 ∪
 (
 T
 (
 X
 )
 ∖
 range
 ⁡
 e
 )
 ,
 
 
 {\displaystyle \operatorname {range} e\subseteq Y\subsetneq X\cup (T(X)\setminus \operatorname {range} e),}
 
 
 
 
 
 
 (
 
 X
 ∪
 (
 Y
 ∖
 range
 ⁡
 e
 )
 ,
 
 δ
 
 (
 Y
 ∖
 range
 ⁡
 e
 )
 ×
 (
 Y
 ∖
 range
 ⁡
 e
 )
 
 
 ∪
 (
 δ
 (
 e
 (
 x
 )
 ,
 e
 (
 y
 )
 )
 
 )
 
 x
 ,
 y
 ∈
 X
 
 
 ∪
 (
 δ
 (
 e
 (
 x
 )
 ,
 g
 )
 
 )
 
 x
 ∈
 X
 ,
 g
 ∈
 Y
 ∖
 range
 ⁡
 e
 
 
 ∪
 (
 δ
 (
 f
 ,
 e
 (
 y
 )
 
 )
 
 f
 ∈
 Y
 ∖
 range
 ⁡
 e
 ,
 y
 ∈
 X
 
 
 
 )
 
 
 
 {\displaystyle \left(X\cup (Y\setminus \operatorname {range} e),\delta _{(Y\setminus \operatorname {range} e)\times (Y\setminus \operatorname {range} e)}\cup (\delta (e(x),e(y)))_{x,y\in X}\cup (\delta (e(x),g))_{x\in X,g\in Y\setminus \operatorname {range} e}\cup (\delta (f,e(y))_{f\in Y\setminus \operatorname {range} e,y\in X}\right)}
 
 is not hyperconvex.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>: Proposition 4.7.2  ("(T(X),δ) is a hyperconvex hull of (X,d).")</li>
<li>Let 
 
 
 
 (
 H
 ,
 ε
 )
 
 
 {\displaystyle (H,\varepsilon )}
 
 be a hyperconvex metric space with 
 
 
 
 X
 ⊆
 H
 
 
 {\displaystyle X\subseteq H}
 
 and 
 
 
 
 ε
 
 
 |
 
 
 X
 ×
 X
 
 
 =
 δ
 
 
 {\displaystyle \varepsilon |_{X\times X}=\delta }
 
. If for all I with 
 
 
 
 X
 ⊆
 I
 ⊊
 H
 ,
 
 
 {\displaystyle X\subseteq I\subsetneq H,}
 
 
 
 
 
 (
 I
 ,
 ε
 
 
 |
 
 
 I
 ×
 I
 
 
 )
 
 
 {\displaystyle (I,\varepsilon |_{I\times I})}
 
 is not hyperconvex, then 
 
 
 
 (
 H
 ,
 ε
 )
 
 
 {\displaystyle (H,\varepsilon )}
 
 and (T(X),δ) are <a href="/facts/Isometry/K5wX8ah6">isometric</a>.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>: Proposition 4.7.1  ("Every hyperconvex hull of (X,d) is isometric with (T(X),δ).")</li></ul>
<h2 id="examples">Examples</h2>
<ul><li>Say |X|=3, choose distinct a, b, c such that X={a,b,c}, and let i=d(a,b), j=d(a,c), k=d(b,c). Then 
 
 
 
 
 
 
 
 T
 (
 X
 )
 =
 
 
 
 {
 v
 ∈
 (
 
 
 R
 
 
 ≥
 0
 
 
 
 )
 
 3
 
 
 :
 1
 =
 
 v
 
 a
 
 
 +
 
 v
 
 b
 
 
 ,
 2
 =
 
 v
 
 a
 
 
 +
 
 v
 
 c
 
 
 ,
 3
 ≤
 
 v
 
 b
 
 
 +
 
 v
 
 c
 
 
 
 
 
 
 
 
 
 
 
 or 
 
 1
 =
 
 v
 
 a
 
 
 +
 
 v
 
 b
 
 
 ,
 2
 ≤
 
 v
 
 a
 
 
 +
 
 v
 
 c
 
 
 ,
 3
 =
 
 v
 
 b
 
 
 +
 
 v
 
 c
 
 
 
 
 
 
 
 
 
 
 
 or 
 
 1
 ≤
 
 v
 
 a
 
 
 +
 
 v
 
 b
 
 
 ,
 2
 =
 
 v
 
 a
 
 
 +
 
 v
 
 c
 
 
 ,
 3
 =
 
 v
 
 b
 
 
 +
 
 v
 
 c
 
 
 }
 
 
 
 
 =
 
 
 
 {
 v
 ∈
 (
 
 
 R
 
 
 ≥
 0
 
 
 
 )
 
 3
 
 
 :
 
 v
 
 a
 
 
 ≤
 
 
 
 (
 i
 +
 j
 )
 −
 k
 
 2
 
 
 ,
 
 v
 
 b
 
 
 =
 i
 −
 
 v
 
 a
 
 
 ,
 
 v
 
 c
 
 
 =
 j
 −
 
 v
 
 a
 
 
 
 
 
 
 
 
 
 
 
 or 
 
 
 v
 
 a
 
 
 =
 i
 −
 
 v
 
 b
 
 
 ,
 
 v
 
 b
 
 
 ≤
 
 
 
 (
 i
 +
 k
 )
 −
 j
 
 2
 
 
 ,
 
 v
 
 c
 
 
 =
 k
 −
 
 v
 
 b
 
 
 
 
 
 
 
 
 
 
 
 or 
 
 
 v
 
 a
 
 
 =
 j
 −
 
 v
 
 c
 
 
 ,
 
 v
 
 b
 
 
 =
 k
 −
 
 v
 
 c
 
 
 ,
 
 v
 
 c
 
 
 ≤
 
 
 
 (
 j
 +
 k
 )
 −
 i
 
 2
 
 
 }
 
 
 
 
 =
 
 
 
 {
 
 (
 t
 ,
 i
 −
 t
 ,
 j
 −
 t
 )
 :
 t
 ∈
 
 [
 
 0
 ,
 i
 ∧
 j
 ∧
 
 
 
 (
 i
 +
 j
 )
 −
 k
 
 2
 
 
 
 ]
 
 
 }
 
 
 
 
 
 
 
 ∪
 
 {
 
 (
 i
 −
 t
 ,
 t
 ,
 k
 −
 t
 )
 :
 t
 ∈
 
 [
 
 0
 ,
 i
 ∧
 k
 ∧
 
 
 
 (
 i
 +
 k
 )
 −
 j
 
 2
 
 
 
 ]
 
 
 }
 
 
 
 
 
 
 
 ∪
 
 {
 
 (
 j
 −
 t
 ,
 k
 −
 t
 ,
 t
 )
 :
 t
 ∈
 
 [
 
 0
 ,
 j
 ∧
 k
 ∧
 
 
 
 (
 j
 +
 k
 )
 −
 i
 
 2
 
 
 
 ]
 
 
 }
 
 
 
 
 
 =
 
 
 
 {
 
 (
 t
 ,
 i
 −
 t
 ,
 j
 −
 t
 )
 :
 t
 ∈
 
 [
 
 0
 ,
 
 
 
 (
 i
 +
 j
 )
 −
 k
 
 2
 
 
 
 ]
 
 
 }
 
 
 
 
 
 
 
 ∪
 
 {
 
 (
 i
 −
 t
 ,
 t
 ,
 k
 −
 t
 )
 :
 t
 ∈
 
 [
 
 0
 ,
 
 
 
 (
 i
 +
 k
 )
 −
 j
 
 2
 
 
 
 ]
 
 
 }
 
 
 
 
 
 
 
 ∪
 
 {
 
 (
 j
 −
 t
 ,
 k
 −
 t
 ,
 t
 )
 :
 t
 ∈
 
 [
 
 0
 ,
 
 
 
 (
 j
 +
 k
 )
 −
 i
 
 2
 
 
 
 ]
 
 
 }
 
 
 
 
 
 =
 
 
 conv
 ⁡
 {
 (
 0
 ,
 i
 ,
 j
 )
 ,
 x
 }
 ∪
 conv
 ⁡
 {
 (
 i
 ,
 0
 ,
 k
 )
 ,
 x
 }
 ∪
 conv
 ⁡
 {
 (
 j
 ,
 k
 ,
 0
 )
 ,
 x
 }
 ,
 
 
 
 
 
 
 {\displaystyle {\begin{alignedat}{2}T(X)=&\{v\in (\mathbb {R} _{\geq 0})^{3}:1=v_{a}+v_{b},2=v_{a}+v_{c},3\leq v_{b}+v_{c}\\&\qquad \qquad \qquad {\text{or }}1=v_{a}+v_{b},2\leq v_{a}+v_{c},3=v_{b}+v_{c}\\&\qquad \qquad \qquad {\text{or }}1\leq v_{a}+v_{b},2=v_{a}+v_{c},3=v_{b}+v_{c}\}\\=&\{v\in (\mathbb {R} _{\geq 0})^{3}:v_{a}\leq {\frac {(i+j)-k}{2}},v_{b}=i-v_{a},v_{c}=j-v_{a}\\&\qquad \qquad \qquad {\text{or }}v_{a}=i-v_{b},v_{b}\leq {\frac {(i+k)-j}{2}},v_{c}=k-v_{b}\\&\qquad \qquad \qquad {\text{or }}v_{a}=j-v_{c},v_{b}=k-v_{c},v_{c}\leq {\frac {(j+k)-i}{2}}\}\\=&\left\{(t,i-t,j-t):t\in \left[0,i\land j\land {\frac {(i+j)-k}{2}}\right]\right\}\\&\cup \left\{(i-t,t,k-t):t\in \left[0,i\land k\land {\frac {(i+k)-j}{2}}\right]\right\}\\&\cup \left\{(j-t,k-t,t):t\in \left[0,j\land k\land {\frac {(j+k)-i}{2}}\right]\right\}\\=&\left\{(t,i-t,j-t):t\in \left[0,{\frac {(i+j)-k}{2}}\right]\right\}\\&\cup \left\{(i-t,t,k-t):t\in \left[0,{\frac {(i+k)-j}{2}}\right]\right\}\\&\cup \left\{(j-t,k-t,t):t\in \left[0,{\frac {(j+k)-i}{2}}\right]\right\}\\=&\operatorname {conv} \{(0,i,j),x\}\cup \operatorname {conv} \{(i,0,k),x\}\cup \operatorname {conv} \{(j,k,0),x\},\end{alignedat}}}
 
 where 
 
 
 
 x
 =
 
 2
 
 −
 1
 
 
 (
 i
 +
 j
 −
 k
 ,
 i
 +
 k
 −
 j
 ,
 j
 +
 k
 −
 i
 )
 .
 
 
 {\displaystyle x=2^{-1}(i+j-k,i+k-j,j+k-i).}
 
 [Add a picture. Caption: If X={0,1,2}, then T(X)=conv{(,,),(,,)} u conv{(,,),(,,)} u conv{(,,),(,,)} is shaped like the letter Y.] (Cf. <a class="footnote-ref" id="fnref:23" href="#fn:23">23</a>: 124 )</li></ul>

<ul><li>The figure shows a set X of 16 points in the plane; to form a finite metric space from these points, we use the <a href="/facts/Manhattan_distance/zU7gGUPv">Manhattan distance</a> (ℓ1 distance).<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> The blue region shown in the figure is the <a href="/facts/Orthogonal_convex_hull/XRxv9Qg1">orthogonal convex hull</a>, the set of points z such that each of the four closed quadrants with z as apex contains a point of X. Any such point z corresponds to a point of the tight span: the function f(x) corresponding to a point z is f(x) = d(z,x). A function of this form satisfies property 1 of the tight span for any z in the Manhattan-metric plane, by the triangle inequality for the Manhattan metric. To show property 2 of the tight span, consider some point x in X; we must find y in X such that f(x)+f(y)=d(x,y). But if x is in one of the four quadrants having z as apex, y can be taken as any point in the opposite quadrant, so property 2 is satisfied as well. Conversely it can be shown that every point of the tight span corresponds in this way to a point in the orthogonal convex hull of these points. However, for point sets with the Manhattan metric in higher dimensions, and for planar point sets with disconnected orthogonal hulls, the tight span differs from the orthogonal convex hull.</li></ul>
<h2 id="dimension-of-the-tight-span-when-xis-finite">Dimension of the tight span when X is finite</h2>
The definition above embeds the tight span T(X) of a set of n (
 
 
 
 n
 ∈
 
 
 Z
 
 
 ≥
 0
 
 
 
 
 {\displaystyle n\in \mathbb {Z} _{\geq 0}}
 
) points into RX, a real vector space of dimension n. On the other hand, if we consider the dimension of T(X) as a <a href="/facts/Polyhedral_complex/T6YMhC4w">polyhedral complex</a>, Develin (2006) showed that, with a suitable general position assumption on the metric, this definition leads to a space with dimension between n/3 and n/2.

<h2 id="alternative-definitions">Alternative definitions</h2>
An alternative definition based on the notion of a <a href="/facts/Metric_space_aimed_at_its_subspace/qllBKasu">metric space aimed at its subspace</a> was described by Holsztyński (1968), who proved that the injective envelope of a Banach space, in the category of Banach spaces, coincides (after forgetting the linear structure) with the tight span. This theorem allows to reduce certain problems from arbitrary Banach spaces to Banach spaces of the form C(X), where X is a compact space.
Develin & Sturmfels (2004) attempted to provide an alternative definition of the tight span of a finite metric space as the <a href="/facts/Tropical_geometry/fFy8Evgv">tropical convex hull</a> of the vectors of distances from each point to each other point in the space. However, later the same year they acknowledged in an Erratum Develin & Sturmfels (2004a) that, while the tropical convex hull always contains the tight span, it may not coincide with it.

<h2 id="applications">Applications</h2>
<ul><li>Dress, Huber & Moulton (2001) describe applications of the tight span in <a href="/facts/Phylogenetics/bw4rsovt">reconstructing evolutionary trees</a> from biological data.</li>
<li>The tight span serves a role in several <a href="/facts/Online_algorithm/64TsU7Yz">online algorithms</a> for the <a href="/facts/K-server_problem/josxwUPX">K-server problem</a>.<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a></li>
<li>Sturmfels & Yu (2004) uses the tight span to classify metric spaces on up to six points.</li>
<li>Chepoi (1997) uses the tight span to prove results about packing cut metrics into more general finite metric spaces.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Kuratowski_embedding/Jd4dao5W">Kuratowski embedding</a>, an embedding of any metric space into a <a href="/facts/Banach_space/sDEIk7EC">Banach space</a> defined similarly to the Kuratowski map</li>
<li><a href="/facts/Injective_metric_space/kExQ3lST">Injective metric space</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Chepoi, Victor (1997), "A TX approach to some results on cuts and metrics", Advances in Applied Mathematics, 19 (4): 453–470, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Faama.1997.0549">10.1006/aama.1997.0549</a>.</li>
<li><a href="/facts/Marek_Chrobak/YrLlChdY">Chrobak, Marek</a>; <a href="/facts/Lawrence_L._Larmore/r4vy1vqk">Larmore, Lawrence L.</a> (1994), "Generosity helps or an 11-competitive algorithm for three servers", Journal of Algorithms, 16 (2): 234–263, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjagm.1994.1011">10.1006/jagm.1994.1011</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:15169525">15169525</a>.</li>
<li><a href="/facts/Mike_Develin/gjjAlRHy">Develin, Mike</a> (2006), "Dimensions of tight spans", <a href="/facts/Annals_of_Combinatorics/2v3tCE7a">Annals of Combinatorics</a>, 10 (1): 53–61, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math.CO/0407317">math.CO/0407317</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00026-006-0273-y">10.1007/s00026-006-0273-y</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:92984638">92984638</a>.</li>
<li><a href="/facts/Mike_Develin/gjjAlRHy">Develin, Mike</a>; <a href="/facts/Bernd_Sturmfels/BejRHlNI">Sturmfels, Bernd</a> (2004), <a href="http://www.math.uiuc.edu/documenta/vol-09/01.pdf">"Tropical convexity"</a> (PDF), Documenta Mathematica, 9: 1–27, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4171%2Fdm%2F154">10.4171/dm/154</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:64471">64471</a>.</li>
<li><a href="/facts/Mike_Develin/gjjAlRHy">Develin, Mike</a>; <a href="/facts/Bernd_Sturmfels/BejRHlNI">Sturmfels, Bernd</a> (2004a), <a href="https://www.math.uni-bielefeld.de/documenta/vol-09/12.pdf">"Erratum for "Tropical Convexity""</a> (PDF), Documenta Mathematica, 9: 205–206, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.4171%2Fdm%2F154">10.4171/dm/154</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:64471">64471</a>.</li>
<li><a href="/facts/Andreas_Dress/9lgm32G3">Dress, Andreas W. M.</a> (1984), "Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups", <a href="/facts/Advances_in_Mathematics/kXtcl4pM">Advances in Mathematics</a>, 53 (3): 321–402, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0001-8708%2884%2990029-X">10.1016/0001-8708(84)90029-X</a>.</li>
<li><a href="/facts/Andreas_Dress/9lgm32G3">Dress, Andreas W. M.</a>; <a href="/facts/Katharina_T._Huber/wpqQTlvB">Huber, K. T.</a>; Moulton, V. (2001), <a href="http://www.math.uiuc.edu/documenta/lsu/dress-huber-multon.pdf">"Metric spaces in pure and applied mathematics"</a> (PDF), Documenta Mathematica (Proceedings Quadratic Forms LSU): 121–139.</li>
<li>Holsztyński, Włodzimierz (1968), "Linearisation of isometric embeddings of Banach Spaces. Metric Envelopes.", Bull. Acad. Polon. Sci., 16: 189–193.</li>
<li><a href="/facts/John_R._Isbell/Pjyygred">Isbell, J. R.</a> (1964), "Six theorems about injective metric spaces", <a href="/facts/Comment._Math._Helv./ddjErBn3">Comment. Math. Helv.</a>, 39: 65–76, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF02566944">10.1007/BF02566944</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:121857986">121857986</a>.</li>
<li><a href="/facts/Bernd_Sturmfels/BejRHlNI">Sturmfels, Bernd</a>; Yu, Josephine (2004), <a href="http://www.combinatorics.org/Volume_11/Abstracts/v11i1r44.html">"Classification of Six-Point Metrics"</a>, The Electronic Journal of Combinatorics, 11: R44, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math.MG/0403147">math.MG/0403147</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2004math......3147S">2004math......3147S</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.37236%2F1797">10.37236/1797</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6733896">6733896</a>.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li>Joswig, Michael, <a href="http://homepages.math.tu-berlin.de/~joswig/tightspans/index.html">Tight spans</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Dress, Huber & Moulton (2001). - Dress, Andreas W. M.; Huber, K. T.; Moulton, V. (2001), "Metric spaces in pure and applied mathematics" (PDF), Documenta Mathematica (Proceedings Quadratic Forms LSU): 121–139 <a href="http://www.math.uiuc.edu/documenta/lsu/dress-huber-multon.pdf" target="_blank">http://www.math.uiuc.edu/documenta/lsu/dress-huber-multon.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Khamsi and Kirk use this condition in their definition. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Khamsi and Kirk's proof shows one implication of the equivalence to the condition immediately above. The other implication is not difficult to show. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Dress, Andreas; Huber, Katharina T.; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). Basic Phylogenetic Combinatorics. Cambridge University Press. ISBN 978-0-521-76832-0. <a href="978-0-521-76832-0" target="_blank">978-0-521-76832-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">I.e., the Kuratowski map 
 
 
 
 e
 (
 x
 )
 ∈
 T
 (
 X
 )
 .
 
 
 {\displaystyle e(x)\in T(X).}
 
 We will introduce the Kuratowski map below. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). Phylogenetic Networks: Conceps, Algorithms and Applications. Cambridge University Press. ISBN 978-0-521-75596-2. <a href="978-0-521-75596-2" target="_blank">978-0-521-75596-2</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Deza, Michel Marie; Deza, Elena (2014). Encyclopedia of Distances (Third ed.). Springer. p. 47. ISBN 978-3-662-44341-5. <a href="978-3-662-44341-5" target="_blank">978-3-662-44341-5</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Melleray, Julien (2008). "Some geometric and dynamical properties of the Urysohn space". Topology and Its Applications. 155 (14): 1531–1560. doi:10.1016/j.topol.2007.04.029. <a href="https://doi.org/10.1016%2Fj.topol.2007.04.029" target="_blank">https://doi.org/10.1016%2Fj.topol.2007.04.029</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">The supremum is achieved with y=x. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Benyamini, Yoav; Lindenstrauss, Joram (2000). Geometric Nonlinear Functional Analysis. American Mathematical Society. p. 32. ISBN 978-0-8218-0835-1. <a href="978-0-8218-0835-1" target="_blank">978-0-8218-0835-1</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">The supremum is achieved with y=x. <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). Phylogenetic Networks: Conceps, Algorithms and Applications. Cambridge University Press. ISBN 978-0-521-75596-2. <a href="978-0-521-75596-2" target="_blank">978-0-521-75596-2</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Dress, Andreas; Huber, Katharina T.; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). Basic Phylogenetic Combinatorics. Cambridge University Press. ISBN 978-0-521-76832-0. <a href="978-0-521-76832-0" target="_blank">978-0-521-76832-0</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Dress, Andreas; Huber, Katharina T.; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). Basic Phylogenetic Combinatorics. Cambridge University Press. ISBN 978-0-521-76832-0. <a href="978-0-521-76832-0" target="_blank">978-0-521-76832-0</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Khamsi, Mohamed A.; Kirk, William A. (2001). An Introduction to Metric Spaces and Fixed Point Theory. Wiley. <a href="/wiki/Mohamed_Amine_Khamsi" target="_blank">/wiki/Mohamed_Amine_Khamsi</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). Phylogenetic Networks: Conceps, Algorithms and Applications. Cambridge University Press. ISBN 978-0-521-75596-2. <a href="978-0-521-75596-2" target="_blank">978-0-521-75596-2</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">In two dimensions, the Manhattan distance is isometric after rotation and scaling to the ℓ∞ distance, so with this metric the plane is itself injective, but this equivalence between ℓ1 and ℓ∞ does not hold in higher dimensions. <a href="/wiki/Lp_space#General_ℓp-space" target="_blank">/wiki/Lp_space#General_ℓp-space</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Chrobak & Larmore (1994). - Chrobak, Marek; Larmore, Lawrence L. (1994), "Generosity helps or an 11-competitive algorithm for three servers", Journal of Algorithms, 16 (2): 234–263, doi:10.1006/jagm.1994.1011, S2CID 15169525 <a href="https://doi.org/10.1006%2Fjagm.1994.1011" target="_blank">https://doi.org/10.1006%2Fjagm.1994.1011</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
</ol>

Tight span open-in-new

Tight span