Computing the Skorokhod distance between polygonal traces
Computing the Skorokhod distance between polygonal traces
复制标题
计算多边形轨迹之间的 Skorokhod 距离
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Vinayak S. Prabhu
中科院分区：
文献类型：
--
作者：
R. Majumdar;Vinayak S. Prabhu
Skorokhod距离是连续和混合系统迹的自然度量。它测量两个轨迹之间的最佳匹配，每个轨迹将时间间隔[0，T]映射到度量空间O，当允许连续双射定时失真时。形式上，它计算所有时序失真上两个分量的最大值的下确界：第一个分量量化时序失真的时序差异，第二个分量量化时序失真后值的失配（在度量空间O中）。Skorokhod距离出现在各种基本的混合动力系统分析关注：从混合动力系统的语义和等价概念的定义，以实际问题，如检查模型的接近度或模拟的质量。尽管它在语义上的广泛使用，两个有限采样时间的混合轨迹之间的Skorokhod距离的计算问题仍然是开放的。我们解决的问题，计算两个多边形轨迹之间的Skorokhod距离（这些轨迹出现时，采样时间的轨迹是由采样点之间的线性插值完成）。我们提供了一个算法来计算精确的Skorokhod距离时，跟踪值比较使用的L1，L2和L∞范数在n维。我们的算法，减少Fréchet距离的基础上，是完全多项式时间，并采用了新的多项式时间程序的一组几何图元在IRn的三个规范。
The Skorokhod distance is a natural metric on traces of continuous and hybrid systems. It measures the best match between two traces, each mapping a time interval [0, T] to a metric space O, when continuous bijective timing distortions are allowed. Formally, it computes the infimum, over all timing distortions, of the maximum of two components: the first component quantifies the timing discrepancy of the timing distortion, and the second quantifies the mismatch (in the metric space O) of the values after the timing distortion. Skorokhod distances appear in various fundamental hybrid systems analysis concerns: from definitions of hybrid systems semantics and notions of equivalence, to practical problems such as checking the closeness of models or the quality of simulations. Despite its extensive use in semantics, the computation problem for the Skorokhod distance between two finite sampled-time hybrid traces remained open. We address the problem of computing the Skorokhod distance between two polygonal traces (these traces arise when sampled-time traces are completed by linear interpolation between sample points). We provide an algorithm to compute the exact Skorokhod distance when trace values are compared using the L1, L2, and L∞ norms in n dimensions. Our algorithm, based on a reduction to Fréchet distances, is fully polynomial-time, and incorporates novel polynomial-time procedures for a set of geometric primitives in IRn over the three norms.