Tight spans are polyhedral complexes which can be associated to any finite metric space. If the metric is tree-like then the tight span is a geometric realization of the tree with proper edge lengths. In general, it can be understood as an object which encompasses all trees which could possible fit the given metric.
H.-J. Bandelt and A. Dress: Reconstructing the shape of a tree from observed dissimilarity data, Adv. in Appl. Math. 7 (1986), no. 3, 309-343; MR0858908 (87k:05060).
We start out by creating a file (assume that it is called my.poly
) containing a section
METRIC and a section TAXA . The former defines the metric space in terms of a (symmetric)
distance matrix, the latter are labels for the rows (and columns).
The tight span associated with this finite metric space is the bounded subcomplex of a polyhedron given in terms of inequalities. The client metric2poly makes these INEQUALITIES explicit. If the file contains a proper header which identifies the object defined as a tight span then this step is not necessary.
Hereafter, all the commands available to polyhedra can be applied to this object. For instance, this is how we see that this tight span lives inside a non-simple unbounded polyhedron.
There are several ways to visualize a tight span, the easiest being to visualize just (the combinatorics of) its graph.
The output is the left image below. Note that the VERTEX_LABELS are produced from the TAXA along with the combinatorics.
The right image has been obtained from:
This command tries to draw the graph metrically correctly (that is, with proper edge lengths), which is usually not possible, since it lives in high-dimensional space. Nonetheless, these images can be useful sometimes.