An algorithm for computing cutpoints in finite metric spaces

Abstract

The theory of the tight span, a cell complex that can be associated to every metric $D$, offers a unifying view on existing approaches for analyzing distance data, in particular for decomposing a metric $D$ into a sum of simpler metrics as well as for representing it by certain specific edge-weighted graphs, often referred to as realizations of $D$. Many of these approaches involve the explicit or implicit computation of the so-called cutpoints of (the tight span of) $D$, such as the algorithm for computing the "building blocks" of optimal realizations of $D$ recently presented by A. Hertz and S. Varone. The main result of this paper is an algorithm for computing the set of these cutpoints for a metric $D$ on a finite set with $n$ elements in $O(n^3)$ time. As a direct consequence, this improves the run time of the aforementioned $O(n^6)$-algorithm by Hertz and Varone by ``three orders of magnitude''.

17 pages, 1 eps-figure