Approximating The p-Mean Curve of Large Data-Sets

Abstract

A set of piecewise linear functions, called polylines, $P_1,\dots ,P_L$ each with at most $n$ vertices can be simplified into a polyline $M$ with $k$ vertices, such that the Fréchet distances ${\epsilon }_1,\dots ,{\epsilon }_L$ to each of these polylines are minimized under the $L_p$ distance. We call $M$ for $L_p$ with $p\ge 1$ a $p$-mean curve ($p$-MC). We discuss $p\ge 1$, for which $L_p$ distance satisfies the triangle inequality and $p$-mean has not been discussed before for most values $p$. Computing the $p$-mean polyline is NP-hard for $L=\Omega (1)$ and some values of $p$, so we discuss approximation algorithms. We give a $O(n^2\log k)$ time exact algorithm for $L=2$ and $p\ge 1$. Also, we reduce the Fréchet distance to the discrete Fréchet distance which adds a factor $2$ to both $k$ and $\epsilon$. Then we use our exact algorithm to find a $3$-approximation for $L>2$ in $\mathrm{poly}(n,L)$ time. Our method is based on a generalization of the free-space diagram (FSD) for Fréchet distance and composable core-sets for approximate summaries.

References in corpus (3)

• A Comparison and Evaluation of Map Construction Algorithms
• On the hardness of computing an average curve
• On the complexity of the middle curve problem