Matching Random Point Sets with Minimum Distortion

Introduction

How well can two independent random samples $X,Y$ of $n$ points from a metric measure space be matched while preserving pairwise distances? We study this question through the minimum distortion between $X$ and $Y$, viewed as finite metric spaces with the induced metric. Our aim is to understand the typical growth of this distortion with the sample size.

For finite metric spaces $X,Y$ of the same cardinality with at least two points, and a bijection $f:X\to Y$, define

The distortion of a bijection is the product of its maximum expansion and contraction factors. In particular, it is invariant under rescaling either metric. Thus $c(X,Y)$ measures how closely the two metric spaces can be matched.

The minimum distortion between two independent samples can be thought of as a notion of metric variance. It is well known that, for a square-integrable real random variable $A$ and an independent copy $A'$, we have $\operatorname{Var}(A)=\frac{1}{2}\mathbb{E}[(A-A')^2]$. This identity expresses variance through the discrepancy between independent copies, without referring to their mean. Similarly, comparing $X$ and $Y$ through $c(X,Y)$ provides a multiplicative measure of the variability of a random finite metric space, without requiring a definition of its expected metric space.

Main result

In this work, we study the minimum distortion between two copies, $X$ and $Y$, each consisting of $n$ points drawn uniformly and independently from $[0,1]$. We show that even this one-dimensional setting is highly non-trivial and exhibits rich geometric structure. Our main result is the following theorem:

Why typical distortion? The expected distortion is a natural first statistic to consider. In our setting, however, it fails to capture the typical behavior, as $\mathbb{E}[c(X,Y)]=\infty$ for sufficiently large $n$ (see Appendix § 9). The reason is simple: an exceptionally close pair in one sample, with no comparably close pair in the other, forces large distortion under every bijection. Such rare configurations produce a sufficiently heavy tail to make the expectation infinite. We therefore study the order of magnitude distortion encountered with high probability when comparing two random configurations.

How (not) to match points. The simplest bijection matches points in order. Writing $X=\{x_1<\cdots<x_n\}$ and $Y=\{y_1<\cdots<y_n\}$, it sends $x_i$ to $y_i$. The difficulty with this matching is that the smallest gaps in the two samples need not occur at corresponding positions. With high probability, the smallest gap in $X$ has size $n^{-2+o(1)}$, while the gap at the same position in $Y$ has size $n^{-1+o(1)}$. This pair alone requires expansion by a factor $n^{1+o(1)}$. The smallest gap in $Y$ causes the same problem for the inverse map. Thus both Lipschitz constants are $n^{1+o(1)}$, giving distortion $n^{2+o(1)}$ with high probability.

This suggests matching the closest pair in $X$ to the closest pair in $Y$, with both gaps of length $n^{-2+o(1)}$ whp, and extending this partial matching to a bijection with low distortion. This controls the distance ratio for the selected pair, but leaves a geometric constraint on all remaining points. The two pairs can lie in very different parts of the interval: for example, one may lie near an endpoint and the other near the middle. They then divide $[0,1]$ into parts containing very different numbers of points, which need to be matched. We prove that, whp, every bijection matching the minimum gap pair in $X$ to the minimum gap pair in $Y$ has large distortion of order at least $n^{1-o(1)}$.

The main difficulty. A more flexible approach is to match each exceptionally short gap to a suitable gap within a limited distance, without insisting that its partner be the shortest gap in the other sample. The difficulty is then to choose these matches so that they can be completed to a bijection with low distortion. Although exceptionally short gaps involve only a small fraction of the points, matching them with low distortion requires a carefully coordinated mapping of the remaining points, as illustrated in the left panel of Figure 2. In particular, many neighboring pairs at the typical distance of order $1/n$, which initially posed no obstacle, are mapped much farther apart to accommodate the displacement required by the short-gap matches. The oscillations distribute this displacement across the remaining points while controlling expansion in both directions. These oscillations must be coordinated in both samples: nearby points of $X$ must have nearby images in $Y$, and nearby points of $Y$ must have nearby preimages in $X$, within the allowed expansion factor. Searching farther for partners makes short gaps easier to match, but also increases the displacement that these oscillations must accommodate. Balancing these two requirements yields the exponent $2/3$. This balance identifies the relevant scales, but realizing it requires matching nearby short gaps together, resolving conflicts between prescribed matches, and completing the resulting partial matching while controlling expansion in both directions. All these components of the mapping are delicate and have nontrivial interactions. We survey them in the technical overview, § 3.

Vector (PDF)

Related work

Geometric similarity of random point sets in $\mathbb{R}$. A closely related line of work asks whether two independent realizations of the same random process have the same geometry at large scales. Peled [17] studied quantitative versions of this question for random subsets of the line. Basu and Sly [1] subsequently developed a multiscale construction for embeddings of random sequences, resolving the question for Poisson processes on the line: two independent realizations are almost surely roughly isometric. Rough isometries allow both multiplicative and additive errors in distances. We highlight that additive error allows exceptionally short gaps to be mapped to substantially longer ones, whereas our distortion objective requires relative control even for these gaps. More recently, Li, Yu, and Zhen [14] established a contrasting result for independent Bernoulli subsets of a product of two regular trees, which are almost surely not quasi-isometric. These results show how the ambient geometry affects the existence of geometrically controlled correspondences between independent random configurations.

Minimum-distortion bijections in $\mathbb{R}$. The computational problem of finding a minimum-distortion bijection between two prescribed finite metric spaces was studied by Kenyon, Rabani, and Sinclair [13]. For point sets on the line, they gave a polynomial-time algorithm that finds an optimal bijection when the minimum distortion is below a fixed constant, with a subsequent work by Chandran et al. [4] improving this threshold. Nayeri and Raichel [16] subsequently developed exact and approximation algorithms with running-time bounds in terms of the optimum distortion and the spread of the input, namely its diameter after rescaling the minimum distance to be one. On the hardness side, Hall and Papadimitriou [10] showed that, even for point sets on the line, approximating the minimum distortion within factors growing polynomially with the number of points is NP-hard in the regime of polynomially large optimum distortion. We prove that when the two point sets are random, finding a mapping that achieves a near-optimal distortion can be done whp.

Random geometric matching. A related line of work studies matchings between random point sets that keep matched points close to one another. Goel, Rai, and Krishnamachari [9] studied bottleneck matching between independent uniform samples, minimizing the largest distance between matched points, and used it to establish sharp thresholds for random geometric graphs. Holroyd, Pemantle, Peres, and Schramm [11] studied invariant perfect matchings between independent Poisson processes, focusing on the tail of the distance from a typical point to its partner. More recently, Elboim, Spinka, and Yakir [8] studied invariant perfect matchings between randomly perturbed lattices and the lattice, obtaining optimal tail bounds under suitable assumptions on the perturbations.

Mappings to grids and lattices. The classical work of Burago and Kleiner [3] and McMullen [15] shows that, in dimensions at least two, even uniformly separated point sets with bounded holes need not admit a bi-Lipschitz bijection to a lattice. Therefore, obstructions to bounded distortion can arise even in the absence of exceptionally close pairs. For finite lattice subsets, Dymond, Kaluža, and Kopecká [7] showed that the minimum Lipschitz constant of a bijection onto a regular grid can be arbitrarily large. Dymond [6] subsequently obtained polylogarithmic upper bounds for suitable random lattice subsets. These finite grid-mapping problems concern one-sided Lipschitz control and a prescribed regular target, while our problem requires control in both directions between two random samples.

Organization of the paper

We begin with the probabilistic estimates and metric reductions used throughout the paper in Section 2. In Section 3, we explain the origin of the $2/3$ exponent and outline the proofs of the lower and upper bounds. Next, in Section 4, we relate displacement to distortion in the equally spaced model (where we study permutations of $[n]$ and their distortion), yielding a short proof of the lower bound in Section 5. We present the upper-bound construction in Section 6.

Use of AI. The proof strategy of the main theorem was developed by the authors, yet we incorporated a simplification found by AI. ChatGPT-6 suggested using the exponential representation in Proposition 2.3 to replace our previous balls and bins type argument which allowed to use the independence of the gaps in the exponential model, and to simplify the approach behind the proof of Proposition 6.5. After this simplification, we realized that our previous $n^{2/3+o(1)}$ upper bound, should yield an $n^{2/3}(\log n)^{O(1)}$ upper bound, when choosing the parameters more delicately. We subsequently used ChatGPT-6 to choose the parameters for this refinement. We used ChatGPT-6 extensively to assist with writing the paper and generating the figures.

After completing the main results we conjectured that controlling displacement through oscillations, as we did in the upper bound, is necessary. We asked the model to prove the existence of oscillating permutation minors in any permutation with distortion and displacement nearly equal. ChatGPT-6 supplied the proof (and defined woven permutations) appearing in Appendix § 8. One component of the AI’s proof, Lemma A.6, provides a shorter proof to Theorem 4.1. We decided to retain our original proof in the main body of the paper.

Acknowledgments We thank Uri Grupel for useful discussions.

Preliminaries

Throughout, let $n \ge2$. We denote an $n$-point set $Z \subseteq\mathbb{R}$, by $Z = \{z_1 < \cdots< z_n\}$. Let $\mathcal{O}$ denote the distribution of the random set $Z = \{U_1,\ldots,U_n\}$, where $U_1,\ldots,U_n$ are iid uniform random variables on $[0,1]$. These variables are distinct almost surely, so $Z$ has size $n$ almost surely. For $1 \le i < n$, define $\Delta_i^Z = z_{i+1} - z_i$, and put $\Delta_{\min}^Z = \min_{1 \le i < n}\Delta_i^Z$.

The following proposition is a well-known exponential representation of uniform spacings (see [18 Sec. 4.1] or [5 Ch. V, Thm. 2.2]).

The following observation follows trivially from the definition of Lipschitz constant of a function.

This observation combined with Proposition 2.1 allows us to reformulate our problem.

In order to bound $c(X,Y)$ from above we need to present some bijection $f:X \to Y$ with small Lipschitz constants. The following claim shows that we only need bound the quantities $\frac{|f(x_2)-f(x_1)|}{x_2-x_1}$ and $\frac{|f^{-1}(y_2)-f^{-1}(y_1)|}{y_2-y_1}$ for the nearby pairs of points $x_1,x_2 \in X$ and $y_1,y_2 \in Y$.