Fast Metric Decompositions in High Dimension

Abstract

Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of $n$-point sets in ${\ell }_{\infty }$ and ${\ell }_2$ spaces of high dimension $d$. For ${\ell }_{\infty }$, we design a padded-decomposition algorithm that runs in time $\tilde{O}(n{d}^2)$, which is near-linear in $n$, and achieves padding parameter $\tilde{O}(\log n)$. Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of ${\ell }_{\infty }$ [Indyk, JCSS'01], and utilizes recent reductions between covers and decompositions [Conroy and Filtser, STOC'25]. For ${\ell }_2$, we design a separating-decomposition algorithm that achieves near optimal separation $\tilde{O}(\sqrt{\log n})$ in almost-linear time $n^{1+o(1)}$. Our bounds improve over known algorithms with similar running time by a factor $\Omega (\sqrt{\log n})$, and the techniques have additional applications to spanners and nearest-neighbor search.

17 pages