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

How to Create a Tight Span

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

METRIC 0 1535 2815 1988 1827 1522 1535 0 1864 727 677 926 2815 1864 0 1442 1114 1672 1988 727 1442 0 280 1125 1827 677 1114 280 0 870 1522 926 1672 1125 870 0 TAXA Athens Berlin Lisboa London Paris Rome

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.

> metric2poly my.poly

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.

> polymake my.poly SIMPLE BOUNDED SIMPLE 0 BOUNDED 0

Special Visualization

There are several ways to visualize a tight span, the easiest being to visualize just (the combinatorics of) its graph.

> polymake my.poly VISUAL_BOUNDED_GRAPH VERTEX_LABELS

The output is the left image below. Note that the VERTEX_LABELS are produced from the TAXA along with the combinatorics.

VISUAL_BOUNDED_GRAPH VERTEX_LABELS

The right image has been obtained from:

> polymake my.poly VISUAL_TIGHT_SPAN

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.