Fine-Grained Complexity of Continuous Euclidean k-Center
OPEN ACCESS
Loading...
Author / Creator
Date
2026-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Scopus:
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
In the (continuous) Euclidean k-center problem, given n points in ℝd and an integer k, the goal is to find k center points in ℝd that minimize the maximum Euclidean distance from any input point to its closest center. In this paper, we establish conditional lower bounds for this problem in constant dimensions in two settings.
Parameterized by k: Assuming the Exponential Time Hypothesis (ETH), we show that there is no f(k)no(k1−1/d)-time algorithm for the Euclidean k-center problem. This result shows that the algorithm of Agarwal and Procopiuc [SODA 1998; Algorithmica 2002] is essentially optimal. Furthermore, our lower bound rules out any (1+ε)-approximation algorithm running in time (k/ε)o(k1−1/d)nO(1), thereby establishing near-optimality of the corresponding approximation scheme by the same authors.
Small k: Assuming the 3-SUM hypothesis, we prove that for any ε>0 there is no O(n2−ε)-time algorithm for the Euclidean 2-center problem in ℝ3. This settles an open question posed by Agarwal, Ben Avraham, and Sharir [SoCG 2010; Computational Geometry 2013]. In addition, under the same hypothesis, we prove that for any ε > 0, the Euclidean 6-center problem in ℝ2 also admits no O(n2−ε)-time algorithm.
The technical core of all our proofs is a novel geometric embedding of a system of linear equations. We construct a point set where each variable corresponds to a specific collection of points, and the geometric structure ensures that a small-radius clustering is possible if and only if the system has a valid solution.
Permanent link
Publication status
published
External links
Editor
Book title
STOC '26: Proceedings of the 58th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
330 - 341
Publisher
Association for Computing Machinery
Event
58th Annual ACM Symposium on Theory of Computing (STOC 2026)
Edition / version
Methods
Geographic location
Date collected
Date created
Subject
Euclidean clustering; k-center; Parameterized complexity; Finegrained complexity