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.  ACM Subject Classification Clustering is an important tool in data analysis, used to split data into groups of similar objects. Their dissimilarity is often based on distance between points in Euclidean space. However, the dissimilarity of (polygonal) curves is more accurately measured by specialised measures: Dynamic Time Warping (DTW) [18] , continuous and discrete Fréchet distance [1, 8] . We focus on centroid-based clustering, where each cluster has a centre curve and the quality of the clustering is based on the similarity between the centre and the elements inside the cluster. In particular, given a distance measure δ, we consider the following problems: Problem 1 (k-median for curves with distance δ). Given a set G = {g 1 , . . . , g m } of polygonal curves, find a set C = {c 1 , . . . c k } of polygonal curves that minimizes Problem 2 (k-center for curves with distance δ). Given a set G = {g 1 , . . . , g m } of polygonal curves, find a set C = {c 1 , . . . c k } of polygonal curves that minimizes max The k-median problem for general metric spaces is well studied, often in the context of the closely related facility location problem [14, 13, 15] . Usually, they consider what we will call the discrete k-median problem, where the centers must be selected from the set of input points. In this paper, we are interested in the unconstrained k-median problem, where the centers can be any element of the metric space. Often, we will simply write k-median problem arXiv:1902.08053v1 [cs.CG]
Even more recently REF showed that the k-median problem is also NP-hard for k = 1 and improved upon the aforementioned (1 + ε)-approximations.
On the hardness of computing an average curve
ArXiv
ArXiv
Mathematics Computer Science