Approximating p-Mean Curve of Large Data-Sets
share
Given p, k and a set of polygonal curves P_1,…,P_L, the p-mean curve M of P_1,…,P_L is the curve with at most k vertices that minimizes the L_p norm of the vector of Fréchet distances between each P_i and M. Also, the p-mean curve is the cluster representative (center) of L_p-based clusterings such as k-center, k-medians, and k-means. For p→∞, this problem is known to be NP-hard, with lower bound 2.25-ϵ on its approximation factor for any ϵ>0. By relaxing the number of vertices to O(k), we were able to get constant factor approximation algorithms for p-mean curve with p=O(1) and p→∞, for curves with few changes in their directions.
READ FULL TEXT