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