## Abstract

The Fréchet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fréchet distance. In particular, we give (1 + ∈)-approximation algorithms for variations of the following problem with parameters k and ℓ. Given n univariate time series P, each of complexity at most m, we find k time series, not necessarily from P, which we call cluster centers and which each have complexity at most ℓ, such that (a) the maximum distance of an element of P to its nearest cluster center or (b) the sum of these distances is minimized. Our algorithms have running time near-linear in the input size for constant ∈, k and ℓ. To the best of our knowledge, our algorithms are the first clustering algorithms for the Fréchet distance which achieve an approximation factor of (1 + ∈) or better.

Original language | English |
---|---|

Title of host publication | 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 |

Publisher | Association for Computing Machinery, Inc |

Pages | 766-785 |

Number of pages | 20 |

Volume | 2 |

ISBN (Electronic) | 9781510819672 |

Publication status | Published - 2016 |

Event | 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) - Arlington, United States Duration: 10 Jan 2016 → 12 Jan 2016 Conference number: 27 http://www.siam.org/meetings/da16/ |

### Conference

Conference | 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) |
---|---|

Abbreviated title | SODA2016 |

Country/Territory | United States |

City | Arlington |

Period | 10/01/16 → 12/01/16 |

Internet address |

## Keywords

- Approximation algorithms
- Chet distance
- Clustering
- Dynamic time warping
- Fré
- Functional data
- Longitudinal data
- Time series