Abstract
This paper investigates the computational complexity of $k$-median and $k$-means clustering in low-dimensional Euclidean space. Contrary to the "blessing of dimensionality" observed in other geometric problems, the authors prove that these clustering problems remain stubbornly hard. Assuming the Exponential Time Hypothesis (ETH), they show that exact solutions require $n^{\Omega(k)}$ time in dimensions as low as 4, and $n^{\Omega(\sqrt{k})}$ in 2D, matching known upper bounds.
Introduction
In computational geometry, the "curse of dimensionality" typically refers to problems becoming exponentially harder as the number of features increases. Conversely, many problems like the Traveling Salesman Problem (TSP) enjoy a "limited blessing," where low-dimensional Euclidean space allows for significantly faster algorithms than general graphs. For clustering, it has long been known that $k$-median and $k$-means are NP-hard. However, a central question remained: can we beat the $n^{O(k)}$ brute-force wall for exact clustering in low dimensions?
Methodology: ETH and Geometric Gadgets
The authors employ conditional lower bounds based on the Exponential Time Hypothesis (ETH), which posits that 3-SAT cannot be solved in sub-exponential time. The core of the proof involves reducing the Partial Vertex Cover (PVC) problem to a clustering instance in 3D or 4D space.
To achieve this, they utilize a sophisticated geometric construction involving the moment curve ($t \to (t, t^2, \dots, t^d)$). In high dimensions, it is trivial to make points "near" each other, but low-dimensional geometry usually restricts this. By placing points along the moment curve, the authors construct "pathological" point sets where Voronoi cells intersect in complex, highly controlled ways.
These constructions allow the authors to encode the combinatorial structure of PVC into the geometric distances of the clustering problem. The figures above illustrate the topological logic used to ensure that optimal cluster centers must correspond to valid solutions of the original hard problem.
Key Results and Dimensionality Gaps
The paper establishes several tight bounds for the running time of exact clustering algorithms:
- 4D Euclidean Space: For standard $k$-median and $k$-means, no algorithm can run faster than $n^{o(k)}$ unless ETH is false. This confirms that brute force is essentially the best possible approach for exact solutions in 4D.
- 3D Euclidean Space: The $n^{\Omega(k)}$ lower bound holds for the "penalized" version of $k$-median, where one can pay a fine instead of assigning a point to a cluster.
- 2D Euclidean Space: The authors prove a lower bound of $n^{\Omega(\sqrt{k})}$ for penalized $k$-median and provide a matching upper bound algorithm of $n^{O(\sqrt{k})}$, effectively settling the complexity of the 2D case.
Discussion and Implications
This research highlights a "steep gap" in complexity. While 2D clustering is slightly more tractable, the problem becomes significantly harder as soon as a third or fourth dimension is added.
It is important to distinguish these results from approximation algorithms. While finding the exact optimal clustering is mathematically "too hard" in low dimensions, efficient Polynomial Time Approximation Schemes (PTAS) still exist that can find solutions within $(1+\epsilon)$ of the optimum in linear time. This paper provides the theoretical justification for why we must often settle for these approximations in practice.
Summary updated