Matching Random Point Sets with Minimum Distortion
math.PR, math.CO, math.MG
Submitted: 2026-11-04
Updated: 2026-11-04
Comments: 47 pages, 9 figures. Includes a six-page technical overview explaining the main ideas and proof techniques
License: http://creativecommons.org/licenses/by/4.0/
The gist: How well can two independent random samples from a metric measure space be matched while preserving pairwise distances? Concretely, given two independent copies…
Terminology
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 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.
Sources
- Lipschitz embeddings of random sequences
- Separated nets in Euclidean space and Jacobians of biLipschitz maps
- Lipschitz constant $\log{n}$ almost surely suffices for mapping $n$ grid points onto a cube
- Mapping $n$ grid points onto a square forces an arbitrarily large Lipschitz constant
- Optimal matchings of randomly perturbed lattices
- Monotone properties of random geometric graphs have sharp thresholds
- Quasi-isometric rigidity for random subsets in products of trees
- On rough isometries of Poisson processes on the line
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves