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

arXiv: https://arxiv.org/abs/2511.12564 · HTML: https://mlsanity.com/paper/2511.12564/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 33 references that are in the map.
- First posted on arXiv 16 Nov 2025.

## Builds on (most cited first, 7 of 7)

- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Object Detection in 20 Years: A Survey](https://mlsanity.com/paper/1905.05055/) (2019)
- [Sets Clustering](https://mlsanity.com/paper/2003.04135/) (2020)
- [Tight Sensitivity Bounds For Smaller Coresets](https://mlsanity.com/paper/1907.01433/) (2019)
- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Occlusion-Robust Object Pose Estimation with Holistic Representation](https://mlsanity.com/paper/2110.11636/) (2021)
- [k-Means Clustering of Lines for Big Data](https://mlsanity.com/paper/1903.06904/) (2019)

## Abstract (arXiv)

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.