Tight span

From Wikipedia, the free encyclopedia

You have new messages (last change).
If a set of points in the plane, with the Manhattan metric, has a connected orthogonal convex hull, then that hull coincides with the tight span of the points.
If a set of points in the plane, with the Manhattan metric, has a connected orthogonal convex hull, then that hull coincides with the tight span of the points.

In metric geometry, the tight span of a metric space is an injective metric space into which the finite space can be embedded. In some sense it consists of all points "between" the points of the space, analogous to the convex hull of a point set in a Euclidean space. The tight span is also sometimes known as the injective envelope or hyperconvex hull of the space. It has also been called the injective hull, but should not be confused with an unrelated concept, the injective hull of a module in algebra.

The tight span was first described by Isbell (1964). It was later independently rediscovered by Dress (1984) and Chrobak and Larmore (1994); see Chepoi (1997) for this history. The tight span is one of the central constructions of T-theory.

Contents

[edit] Formal definition

Formally, we can define the tight span of a finite metric space as follows. Let (X,d) be a metric space, with X finite, and let T(X) be the set of functions from X to R such that

  1. For any x, y in X, f(x) + f(y) ≥ d(x,y), and
  2. For each x in X, there exists y in X such that f(x) + f(y) = d(x,y).[1]

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 triangle inequality together with the distances in (X,d). The second requirement states that none of these distances can be reduced without violating the triangle inequality.

Given two functions f and g in T(X), define δ(f,g) = max |f(x)-g(x)|; if we view T(X) as a subset of a vector space R|X| then this is the usual L∞ distance between vectors. The tight span of X is the metric space (T(X),δ). There is an isometric embedding of X into its tight span, given by mapping any x into the function fx(y) = d(x,y). It is straightforward to expand the definition of δ using the triangle inequality for X to show that the distance between any two points of X is equal to the distance between the corresponding points in the tight span.

The definition above embeds the tight span of a set of n points into a space of dimension n. However, Develin (2004) shows that, with a suitable general position assumption on the metric, this definition leads to a space with dimension between n/3 and n/2. Develin and Sturmfels (2004) provide an alternative definition of the tight span of a finite metric space, as the tropical convex hull of the vectors of distances from each point to each other point in the space.

[edit] Example

The figure shows a set X of 16 points in the plane; to form a finite metric space from these points, we use the Manhattan distance (L1 metric).[2] The blue region shown in the figure is the orthogonal convex hull, 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.

[edit] Applications

  • Dress, Huber, and Moulton (2001) describe applications of the tight span in reconstructing evolutionary trees from biological data.
  • The tight span serves a role in several online algorithms for the K-server problem (Chrobak and Larmore 1994).
  • Sturmfels and Yu (2004) uses the tight span to classify metric spaces on up to six points.
  • Chepoi (1997) uses the tight span to prove results about packing cut metrics into more general finite metric spaces.

[edit] Notes

  1. ^ For infinite metric spaces, this property needs to be modified to state that inf f(x) + f(y) - d(x,y) = 0; see e.g. Dress et al (2001).
  2. ^ In two dimensions, the Manhattan distance is isometric after rotation and scaling to the L∞ distance, so with this metric the plane is itself injective, but this equivalence between L1 and L∞ does not hold in higher dimensions.

[edit] References

  • Chepoi, Victor (1997). "A TX approach to some results on cuts and metrics". Advances in Applied Mathematics 19 (4): 453–470. DOI:10.1006/aama.1997.0549. 
  • Chrobak, Marek; Larmore, Lawrence L. (1994). "Generosity helps or an 11-competitive algorithm for three servers". Journal of Algorithms 16: 234–263. 
  • Dress, Andreas W. M. (1984). "Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups". Advances in Mathematics 53: 321–402. 
  • Isbell, J. R. (1964). "Six theorems about injective metric spaces". Comment. Math. Helv. 39: 65–76. 

[edit] External links

Retrieved from "http://en.wikipedia.org../../../t/i/g/Tight_span.html"