Citizendia
Your Ad Here

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. Taxicab geometry, considered by Hermann Minkowski in the 19th century is a form of Geometry in which the usual metric of Euclidean geometry In Euclidean geometry, a set K\subset\R^n is defined to be Orthogonally convex if for every line L that is parallel to one of the axes of the Cartesian

In metric geometry, the metric envelope or tight span of a metric space M is an injective metric space into which M can be embedded. In Mathematics, a metric space is a set where a notion of Distance (called a metric) between elements of the set is defined In Mathematics, a metric space is a set where a notion of Distance (called a metric) between elements of the set is defined In Metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a Metric space with certain properties generalizing those In some sense it consists of all points "between" the points of M, analogous to the convex hull of a point set in a Euclidean space. In Mathematics, the convex hull or convex envelope for a set of points X in a Real Vector space V is the minimal Convex The tight span is also sometimes known as the injective envelope or hyperconvex hull of M. 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. In Mathematics, especially in the area of Abstract algebra known as Module theory, the injective hull (or injective envelope) of a module is In Abstract algebra, the concept of a module over a ring is a generalization of the notion of Vector space, where instead of requiring the scalars Algebra is a branch of Mathematics concerning the study of structure, relation, and Quantity.

The tight span was first described by Isbell (1964), and it was studied and applied by Holsztyński in 1960-ties. It was later independently rediscovered by Dress (1984) and Chrobak and Larmore (1994); see Chepoi (1997) for this history. Professor Lawrence L Larmore is a theoretical computer scientist and a professor at University of Nevada Las Vegas. The tight span is one of the central constructions of T-theory. T-theory is a branch of Discrete mathematics dealing with analysis of trees and discrete Metric spaces.

Contents

Definition

The tight span of a metric space X, under the name of metric envelope  I(X), was described by W. Holsztyński (1968) with the help of the notion of metric space aimed at its subspace, as the space of minimal functions of  Aim(X), i. In Mathematics, a metric space aimed at its subspace is a categorical construction that has a direct geometric meaning e. as follows (with notation T(X) in place of I(X)):

T(X) := \{f \in Aim(X) : \forall_{g\in Aim(X)}((g \le f) \Rightarrow (g=f))\}.

In that same 1968 paper he proved that the injective envelope of a Banach space, in the category of Banach spaces, coincides (after forgetting the linear structure) with the injective envelope (called there the metric envelope) in the category of metric spaces and metric mappings. In the mathematical theory of Metric spaces a metric map or short map is a Continuous function between metric spaces that does not increase any 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.

Here is another approach:

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

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). In Mathematics, the triangle inequality states that for any Triangle, the length of a given side must be less than or equal to the sum of the other two sides but greater 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. In Mathematics, the Lp and ℓp spaces are spaces of p-power integrable functions, and corresponding 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). For the Mechanical engineering and Architecture usage see Isometric projection. 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, Holsztyński (1972, published in 1978) and Develin (2004) show 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.

For general (finite and infinite) metric spaces, the tight span may be defined using a modified version of property 2 in the definition above stating that inf f(x) + f(y) - d(x,y) = 0; see e. g. Dress et al (2001).

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). Taxicab geometry, considered by Hermann Minkowski in the 19th century is a form of Geometry in which the usual metric of Euclidean geometry [1] 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. In Euclidean geometry, a set K\subset\R^n is defined to be Orthogonally convex if for every line L that is parallel to one of the axes of the Cartesian 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.

Applications

Notes

  1. ^ 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. In Mathematics, the Lp and ℓp spaces are spaces of p-power integrable functions, and corresponding

References

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic