Curve Simplification and Clustering under Fréchet Distance

Abstract

We present new approximation results on curve simplification and clustering under Fréchet distance. Let $T=\{{\tau }_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 ${\delta }_i>0$ for $i\in [n]$, find a curve $\sigma$ of at most $l$ vertices such that $d_F(\sigma ,{\tau }_i)\le {\delta }_i$ for $i\in [n]$. We present an algorithm that returns a null output or a curve $\sigma$ of at most $l$ vertices such that $d_F(\sigma ,{\tau }_i)\le {\delta }_i+\epsilon {\delta }_{\max }$ for $i\in [n]$, where ${\delta }_{\max }={\max }_{i\in [n]}{\delta }_i$. If the output is null, there is no curve of at most $l$ vertices within a Fréchet distance of ${\delta }_i$ from ${\tau }_i$ for $i\in [n]$. The running time is $\tilde{O}(n^{O(l)}{m}^{O(l^2)}(dl/\epsilon {)}^{O(dl)})$. This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve $\tau$ to another curve $\sigma$, where the vertices of $\sigma$ can be anywhere in $R^d$, so that $d_F(\sigma ,\tau )\le (1+\epsilon )\delta$ and $|\sigma |\le (1+\alpha )\min \{|c|:d_F(c,\tau )\le \delta \}$ for any given $\delta >0$ and any fixed $\alpha ,\epsilon \in (0,1)$. The running time is $\tilde{O}(m^{O(1/\alpha )}(d/(\alpha \epsilon ){)}^{O(d/\alpha )})$. 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 $\Sigma$ of $k$ curves, each of $l$ vertices, such that ${\sum }_{i\in [n]}{\min }_{\sigma \in \Sigma }{d}_F(\sigma ,{\tau }_i)$ is within a factor $1+\epsilon$ of the optimum with probability at least $1-\mu$ for any given $\mu ,\epsilon \in (0,1)$. The running time is $\tilde{O}(n{m}^{O(k{l}^2)}{\mu }^{-O(kl)}(dkl/\epsilon {)}^{O((dkl/\epsilon )\log (1/\mu ))})$.

30 pages; Corrected some wrong descriptions concerning related work; Add some figures for illustration