An Algorithm for Computing Cutpoints in Finite Metric Spaces
An Algorithm for Computing Cutpoints in Finite Metric Spaces
复制标题
DOI：
10.1007/s00357-010-9055-7
复制
发表时间：
2010-09-01
影响因子：
2
通讯作者：
Spillner, Andreas
中科院分区：
文献类型：
--
作者：
Dress, Andreas;Huber, Katharina T.;Spillner, Andreas
紧跨度理论，一个可以与每个度量D相关联的单元复合体，提供了对现有方法的统一观点，用于分析距离数据，特别是将度量D分解为更简单的度量之和以及通过某些特定的边加权图表示它，通常称为D的实现。这些方法中的许多涉及到D的（紧跨度）的所谓割点的显式或隐式计算，例如最近由A. Hertz和S.瓦罗内本文的主要结果是一个算法计算的一组这些割点的度量D上的有限集与n个元素在O（n3）时间。作为一个直接的结果，这将前面提到的O（n6）-算法的运行时间提高了“三个数量级”。
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".