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

David Denisov, Shlomi Dolev, Dan Felmdan +1

We study the $k$-means problem for a set $\mathcal{S}\subseteq {\mathbb{R}}^d$ of $n$ segments, aiming to find $k$ centers $X\subseteq {\mathbb{R}}^d$ that minimize $D(\mathcal{S},X)…