The Bane of Low-Dimensionality Clustering

Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, Alan RoytmanSODA 2018 · DOI

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.

Geometric gadget illustrating a curve intersecting a boundary with the origin O outside, resulting in an even number of intersection points.
A variation of the geometric gadget where the origin O is enclosed by the curve, resulting in an odd number of intersection points, used to encode logical constraints.

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

BibTeX
@inproceedings{cohenaddad2018bane,
  author = {Vincent Cohen-Addad and Arnaud de Mesmay and Eva Rotenberg and Alan Roytman},
  title = {{The Bane of Low-Dimensionality Clustering}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975031.30},
}
Figure