Linear time small coresets for k-mean clustering of segments with applications

We study the k-means problem for a set S subseteq ℝd of n segments, aiming to find k centers X subseteq ℝd that minimize D(S,X) := sumS ∈ S minx ∈ X D(S,x), where D(S,x) := intp ∈ S |p - x| dp measures the total distance from each point along a segment to a center. Variants of this problem include handling outliers, employing alternative distance functions such as M-estimators, weighting distances to achieve balanced clustering, or enforcing unique cluster assignments. For any varepsilon > 0, an varepsilon-coreset is a weighted subset C subseteq ℝd that approximates D(S,X) within a factor of 1 ± varepsilon for any set of k centers, enabling efficient streaming, distributed, or parallel computation. We propose the first coreset construction that provably handles arbitrary input segments. For constant k and varepsilon, it produces a coreset of size O(log2 n) computable in O(nd) time. Experiments, including a real-time video tracking application, demonstrate substantial speedups with minimal loss in clustering accuracy, confirming both the practical efficiency and theoretical guarantees of our method.