# On Coresets for Clustering in Small Dimensional Euclidean Spaces

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2023.

## Built on by (most cited first, 3 of 3)

- [Coreset Selection for Object Detection](https://mlsanity.com/paper/2404.09161/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Sampling](https://mlsanity.com/paper/2609.06394/) (2026)

## Abstract (arXiv)

We consider the problem of constructing small coresets for k-Median in Euclidean spaces. Given a large set of data points Psubset ℝd, a coreset is a much smaller set Ssubset ℝd, so that the k-Median costs of any k centers w.r.t. P and S are close. Existing literature mainly focuses on the high-dimension case and there has been great success in obtaining dimension-independent bounds, whereas the case for small d is largely unexplored. Considering many applications of Euclidean clustering algorithms are in small dimensions and the lack of systematic studies in the current literature, this paper investigates coresets for k-Median in small dimensions. For small d, a natural question is whether existing near-optimal dimension-independent bounds can be significantly improved. We provide affirmative answers to this question for a range of parameters. Moreover, new lower bound results are also proved, which are the highest for small d. In particular, we completely settle the coreset size bound for 1-d k-Median (up to log factors). Interestingly, our results imply a strong separation between 1-d 1-Median and 1-d 2-Median. As far as we know, this is the first such separation between k=1 and k=2 in any dimension.