Simplification of Trajectory Streams

doi:10.1007/s00454-026-00838-6

Simplification of Trajectory Streams

2026-03-01

0

PRE

AI

DOI：10.1007/s00454-026-00838-6

原文链接

原文求助

摘要

En 中文

尽管存在可即时简化轨迹流的软件系统，但符合流式要求的具有质量保证的曲线简化算法却鲜有报道。我们针对R^d空间（d为≥2的常数）中在Fréchet距离dF下的两个问题提出了流式算法。考虑R^d空间中的一条多边形曲线r以流式输入。我们提出一种流式算法，对于任意e∈(0,1)和δ>0，可维护一条曲线a，使得dF(a, r[v(1),v(i)]) ≤ (1+e)δ且|a| ≤ 2opt-2，其中r[v(1),v(i)]为当前流式输入的前缀，opt = min{|a|: dF(a, r[v(1),v(i)]) ≤ δ}。工作存储空间为O(ε^(-α))，其中α = 2(d-1)d/22 + d。当d∈{2,3}时，每个顶点处理时间为O(ε^(-α) log 1/ε)；当d≥4时，处理时间为O(ε^(-α))。因此，整条曲线r可在O(ε^(-α) |r| log 1/ε)时间内完成简化。忽略1/ε的多项式因子，该运行时间比提供相同保证的最佳静态算法快|r|倍。我们另提出一种流式算法，对于任意整数k≥2和任意e∈(0,10/17)，可维护一条曲线a，使得|a| ≤ 2k-2且dF(a, r[v(1),v(i)]) ≤ (1+e)·min{dF(a, r[v(1),v(i)]) : |a|≤k}，其中r[v(1),v(i)]为当前流式输入的前缀。工作存储空间为O((kε^(-α) + ε^(-α-1)) log 1/ε)。当d∈{2,3}时，每个顶点处理时间为O(kε^(-α-1) log₂ 1/ε)；当d≥4时，处理时间为O(kε^(-α-1) log 1/ε)。

Keyword:

Streaming algorithm

Curve simplification

Fr & eacute

chet distance

Simplification of Trajectory Streams

摘要

期刊

机构