We describe an algorithm for finding the tight span of a finite metric space;
the tight span is a construction for embedding arbitrary metrics into
$L_\infty$ spaces analogous to the Euclidean convex hull. Our algorithm is
incremental, and applies to any space for which the tight span is homeomorphic
to a subset of the Euclidean plane. After a new point is added to the metric
space our algorithm can update the tight span in time linear in the number of
points already added; this is optimal with respect to the size of the input, an
$n\times n$ distance matrix. As an application, we improve the running time of
an algorithm of Edmonds for embedding finite metrics into the Manhattan-metric
plane, from $O(n^2\log^2 n)$ to $O(n^2)$.