论文标题
曲线简化和聚类在Fréchet距离下
Curve Simplification and Clustering under Fréchet Distance
论文作者
论文摘要
我们在Fréchet距离下简化曲线和聚类中介绍了新的近似结果。令$ t = \ {τ_i：i \ in [n] \} $为$ m $ $ $ vertices中的$ r^d $中的多边形曲线。令$ l $为$ [m] $的任何整数。我们研究一个广义曲线简化问题：给定错误限制$δ_i> 0 $ for $ i \ in [n] $，在最多$ l $ vertices中找到曲线$σ$，例如$ d_f（σ，τ_i）\leΔ_i$ in [n] $ in [n] $。我们提出了一种算法，该算法最多可以返回$ l $ l $ vertices的null输出或曲线$σ$，以便$ d_f（σ，τ_i）\leΔ_i +δ_i +εδ_ {\ max} $ for $ i \ for $ i \ in [n] $ in [n] $，其中$δ_{\ max max} = $ axmax} $ $ $ $ n]如果输出为零，则最多没有$ l $ $ $ $Δ_i$的曲线，从$τ_i$ for $τ_i$ for $ i \ in [n] $。运行时间为$ \ tilde {o} \ bigl（n^{o（l）} m^{o（l^2）}（dl/ε）^{o（dl）} \ bigr）$。该算法产生了第一个多项式两粒子近似方案，将曲线$τ$简化为另一个曲线$σ$，其中$σ$的顶点可以在$ r^d $中的任何位置，因此$ d_f（σ，σ，τ） \ le（1+α）\ min \ {| c | ：d_f（c，τ）\leδ\} $对于任何给定的$δ> 0 $和任何固定的$α，ε\ in（0,1）$。运行时间为$ \ tilde {o} \ bigl（m^{o（1/α）}（d/（αε））^{o（d/α）} \ bigr）$。 通过将我们的技术与文献中的一些先前结果相结合，我们获得了$（k，l）$ - 中间聚类的近似算法。给定的$ t $，它计算$ l $ curves的$ l $顶点的$σ$，以便$ \ sum_ {i \ in [n]} \ min_} \ min_ {σ\ inσ} d_f（σ，τ_i）$在probimimaus of Probimus coptimus coptimus coptimus coptimus contimusy coptimus contimutive coptimuty contimuty Pyptimuty Attimate的$ 1+ε1倍，至少为$ 1- $ 1- $。 （0,1）$。运行时间为$ \ tilde {o} \ bigl（n m^{o（kl^2）}μ^{ - o（kl）}（dkl/ε）^{o（（（dkl/ε）\ log log（1/μ）} \ bigr）$。
We present new approximation results on curve simplification and clustering under Fréchet distance. Let $T = \{τ_i : i \in [n] \}$ be polygonal curves in $R^d$ of $m$ vertices each. Let $l$ be any integer from $[m]$. We study a generalized curve simplification problem: given error bounds $δ_i > 0$ for $i \in [n]$, find a curve $σ$ of at most $l$ vertices such that $d_F(σ,τ_i) \le δ_i$ for $i \in [n]$. We present an algorithm that returns a null output or a curve $σ$ of at most $l$ vertices such that $d_F(σ,τ_i) \le δ_i + εδ_{\max}$ for $i \in [n]$, where $δ_{\max} = \max_{i \in [n]} δ_i$. If the output is null, there is no curve of at most $l$ vertices within a Fréchet distance of $δ_i$ from $τ_i$ for $i \in [n]$. The running time is $\tilde{O}\bigl(n^{O(l)} m^{O(l^2)} (dl/ε)^{O(dl)}\bigr)$. This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve $τ$ to another curve $σ$, where the vertices of $σ$ can be anywhere in $R^d$, so that $d_F(σ,τ) \le (1+ε)δ$ and $|σ| \le (1+α) \min\{|c| : d_F(c,τ) \le δ\}$ for any given $δ> 0$ and any fixed $α, ε\in (0,1)$. The running time is $\tilde{O}\bigl(m^{O(1/α)} (d/(αε))^{O(d/α)}\bigr)$. By combining our technique with some previous results in the literature, we obtain an approximation algorithm for $(k,l)$-median clustering. Given $T$, it computes a set $Σ$ of $k$ curves, each of $l$ vertices, such that $\sum_{i \in [n]} \min_{σ\in Σ} d_F(σ,τ_i)$ is within a factor $1+ε$ of the optimum with probability at least $1-μ$ for any given $μ, ε\in (0,1)$. The running time is $\tilde{O}\bigl(n m^{O(kl^2)} μ^{-O(kl)} (dkl/ε)^{O((dkl/ε)\log(1/μ))}\bigr)$.
