Matching Random Point Sets with Minimum Distortion
Abstract
How well can two independent random samples from a metric measure space be matched while preserving pairwise distances? Concretely, given two independent copies, each of n points sampled from the space, what is their typical metric distortion as finite n-point metric spaces? We prove that the space [0,1] equipped with the uniform measure already exhibits a rich behavior. We show that with high probability the distortion of the two independent samples is n2/3 up to polylogarithmic factors. The lower bound reflects two competing obstructions. A bijection that maps points close to their original positions or their reflections in [0,1] must expand the smallest gaps, in both directions. On the other hand, we show that large displacement from both the identity and reflection itself forces large distortion. Balancing these obstructions yields the lower-bound exponent 2/3. For the upper bound, we construct a partial matching of the points that maps each gap between consecutive points of length d≲ n−4/3 to a pair at distance Õ(dn1/3), with analogous control in the reverse direction. We then use a delicate multiscale oscillation construction to extend this partial matching to a low-distortion bijection.
Related
- Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution
- Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
- Rigidity of algebraic sets with small distortion
- Minimum Volume Conformal Sets for Multivariate Regression
- On the ℓ2 distortion of random triangulations
BibTeX
@misc{benjamini2026matching,
title = {{Matching Random Point Sets with Minimum Distortion}},
author = {Itai Benjamini and Mark Braverman and Elad Tzalik and Georgii Zakharov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06845},
eprint = {2611.06845},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06845},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Matching Random Point Sets with Minimum Distortion
AU - Itai Benjamini
AU - Mark Braverman
AU - Elad Tzalik
AU - Georgii Zakharov
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06845
UR - https://arxiv.org/abs/2611.06845
AB - How well can two independent random samples from a metric measure space be matched while preserving pairwise distances? Concretely, given two independent copies, each of n points sampled from the space, what is their typical metric distortion as finite n-point metric spaces? We prove that the space [0,1] equipped with the uniform measure already exhibits a rich behavior. We show that with high probability the distortion of the two independent samples is n^2/3 up to polylogarithmic factors. The lower bound reflects two competing obstructions. A bijection that maps points close to their original positions or their reflections in [0,1] must expand the smallest gaps, in both directions. On the other hand, we show that large displacement from both the identity and reflection itself forces large distortion. Balancing these obstructions yields the lower-bound exponent 2/3. For the upper bound, we construct a partial matching of the points that maps each gap between consecutive points of length d≲ n^−4/3 to a pair at distance Õ(dn^1/3), with analogous control in the reverse direction. We then use a delicate multiscale oscillation construction to extend this partial matching to a low-distortion bijection.
ER -