Lipschitz Decompositions of Finite ${\ell }_p$ Metrics

Abstract

Lipschitz decomposition is a useful tool in the design of efficient algorithms involving metric spaces. While many bounds are known for different families of finite metrics, the optimal parameters for $n$-point subsets of ${\ell }_p$, for $p>2$, remained open, see e.g. [Naor, SODA 2017]. We make significant progress on this question and establish the bound $\beta =O({\log }^{1-1/p}n)$. Building on prior work, we demonstrate applications of this result to two problems, high-dimensional geometric spanners and distance labeling schemes. In addition, we sharpen a related decomposition bound for $1<p<2$, due to Filtser and Neiman [Algorithmica 2022].