The k-means for lines is a set of k centers (points) that minimizes the sum of squared distances to a given set of n lines in R^d. This is a straightforward generalization of the k-means problem where the input is a set of n points. Related problems minimize sum of (non-squared) distances, other norms, m-estimators or ignore the t farthest points (outliers) from the k centers. We suggest the first provable PTAS algorithms for these problems that compute (1+epsilon)-approximation in time O(n (n) epsilon^2) for any given epsilon (0, 1), and constant integers k, d, t 1, including support for streaming and distributed input. Experimental results on Amazon EC2 cloud and open source are also provided.
Also there has been work on clustering points with @math lines'' @cite_2 , @cite_19 , @cite_5 , where one finds a set of lines @math such that the set of cylinders with radius @math about these lines covers all the input points @math .
@cite_19 @cite_5 @cite_2
2050831206 1984675750 2029432209
We consider the following instance of projective clustering, known as the 2-line-center problem: Given a set S of n points in R2, cover S by two congruent strips of minimum width. Algorithms that find the optimal solution for this problem have near-quadratic running time. In this paper we present an algorithm that, for any e > 0, computes in time O(n(logn + e-2 log(1 e)) + e-7 2 log(1 e)) a cover of S by two strips of width at most (1 + e)w*. (MATH) Let P be a set of n points in @math k (P) denote the minimum over all k-flats @math of max peP Dist(p, ). We present an algorithm that computes, for any 0 k (P) from each point of P. The running time of the algorithm is dnO(k e5log(1 e)). The crucial step in obtaining this algorithm is a structural result that says that there is a near-optimal flat that lies in an affine subspace spanned by a small subset of points in P. The size of this "core-set" depends on k and e but is independent of the dimension.This approach also extends to the case where we want to find a k-flat that is close to a prescribed fraction of the entire point set, and to the case where we want to find j flats, each of dimension k, that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when k>1 or j>1. We consider the following two instances of the projective clustering problem: Given a set S of n points in Rd and an integer k > 0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w*. This paper contains three main results: (i) For d = 2, we present a randomized algorithm that computes O(k log k) strips of width at most w* that cover S. Its expected running time is O(nk2log4n) if k2 log k ≤ n; for larger values of k, the expected running time is O(n2 3k8 3log14 3n). (ii) For d = 3, a cover of S by O(k log k) slabs of width at most w* can be computed in expected time O(n3 2k9 4polygon(n)).(iii) We compute a cover of S ⊂ Rd by O(dk log k) d-cylinders of diameter at most 8w* in expected time O(dnk3 log4 n). We also present a few extensions of this result.