2009/10/13 by Andreas Dress, Dress, A., Katharina T. Huber +7
Computer Science · Mathematics · #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.0910.2317
openalex publication_date 2009/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n3) time. As a direct consequence, this improves the run time of the aforementioned O(n6)-algorithm by Hertz and Varone by ``three orders of magnitude''.