Matching Random Point Sets with Minimum Distortion

Source: arxiv.org/abs/2611.06845

Itai Benjamini, Mark Braverman, Elad Tzalik, Georgii Zakharov

arXivarxiv/2611.06845Nov 4, 2026math.PRscore 0

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…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.06845
curl -X POST /api/v1/records/arxiv/2611.06845/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06845/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'