k-Means Clustering of Lines for Big Data

This is a straightforward generalization of the k-mean problem where the input is a set of n points instead of lines. We suggest the first PTAS that computes a (1 + ε)-approximation to this problem in time O(n log n) for any constant approximation error ε (0, 1), and constant integers k, d 1.