On the hardness of computing an average curve

Research output: Contribution to journalArticleAcademic

17 Downloads (Pure)


We study the complexity of clustering curves under k-median and k-center objectives in the metric space of the Fréchet distance and related distance measures. The k-center problem has recently been shown to be NP-hard, even in the case where k=1, i.e. the minimum enclosing ball under the Fréchet distance. We extend these results by showing that also the k-median problem is NP-hard for k=1. Furthermore, we show that the 1-median problem is W[1]-hard with the number of curves as parameter. We show this under the discrete and continuous Fréchet and Dynamic Time Warping (DTW) distance. Our result generalizes an earlier result by Bulteau et al. from 2018 for a variant of DTW that uses squared distances. Moreover, closing some gaps in the literature, we show positive results for a variant where the center curve may have complexity at most ℓ under the discrete Fréchet distance. In particular, for fixed k,ℓ and ε, we give (1+ε)-approximation algorithms for the (k,ℓ)-median and (k,ℓ)-center objectives and a polynomial-time exact algorithm for the (k,ℓ)-center objective.
Original languageEnglish
Article number1902.08053v1
Number of pages15
Publication statusPublished - 21 Feb 2019


  • Computational Geometry


Dive into the research topics of 'On the hardness of computing an average curve'. Together they form a unique fingerprint.

Cite this