# Interpolating Bijections of Point Sets in Euclidean Space

Consider two finite point sets $P$ and $Q$ from (the same) Euclidean space, assume that they have the same cardinality $n$ and fix a bijection $\phi:P\to Q$. Define an undirected bipartite graph $G_\phi$ where each $p \in P$ is linked via a single edge to $\phi(p) \in Q$ and this edge has weight $\|p - \phi(p)\|$.

We may now associated a number $m(\phi)$ to $\phi$, namely the maximal edge length in $G_\phi$. Then,

There exists an intermediate point set $S$ along with bijections $\psi:Q \to S$ and $\psi': P \to S$ such that $\max[m(\psi'),m(\psi')] \leq \frac{1}{2}m(\phi)$

Just let $S$ be the set of midpoints of edges in $G_\phi$ and defining the bijections in the obvious way along the edges. Here's my question:

What hypotheses are needed to similarly interpolate between $k$ point sets $P_1, \ldots P_k$ with pairwise bijections defined for $k > 2$?

More precisely, what minimal conditions can one impose on the pairwise bijections $\phi_{ij}:P_i \to P_j$ to deduce the existence of a point set $S$ along with bijections $\psi_\ell:S\to P_\ell$, such that $\max_\ell[m(\psi_\ell)] \leq \alpha\cdot\max_{i,j}[m(\phi_{ij})]$ for some $\alpha < 1$?

• In your example with $k=2$ you allow nonstrict inequality $\le 1/2$... whereas in your question you ask for strict inequality $< \alpha$. I notice that your example fails strict inequality when $\phi(p)=p$ for all $p$. May 7 '12 at 13:29
• That's a typo, I intended $\leq$. Fixing it now. May 7 '12 at 15:18

Impose the condition that the functions $\phi_{ij}$ are closed under composition: $\phi_{bc} \circ \phi_{ab} = \phi_{ac}$. Then the nonstrict version of your inequality holds with $\alpha = \frac{k-1}{k}$. To prove it, enumerate $P_1 = p_{11},...,p_{1N}$, say, then push this enumeration around by the $\phi$'s to get a well-defined enumeration of each of $P_1,...,P_k$. Define $S = s_1,...,s_N$ where $s_n$ is the barycenter of $p_{1n},...,p_{kn}$. Then use the fact that the maximum distance from the barycenter of a $k-1$ simplex to the vertices of that simplex is $\le \frac{k-1}{k}$ times the maximum of the pairwise distances amongst the vertices.
• Thank you, that's good. But is it more restrictive than necessary? For instance, it might suffice to require $\phi_{bc}∘\phi_{ab }$ is just very close to -- instead of coincident with -- $\phi_{ac}$. May 7 '12 at 15:23
• The "closed under composition" condition is used in verifying that the enumerations of $P_1,...,P_k$ are well-defined, which is used in turn to enumerate $S$, which is used in turn to define the bijections $\psi_a : S \to P_a$. I don't know how to define these bijections in a reasonable way otherwise. Perhaps if one of the $P_a$'s has two points that are very close to each other, then something like you suggest could work. May 7 '12 at 15:44
{"ft_lang_label":"__label__en","ft_lang_prob":0.8055688,"math_prob":0.9997373,"size":1155,"snap":"2021-43-2021-49","text_gpt3_token_len":348,"char_repetition_ratio":0.118158124,"word_repetition_ratio":0.022346368,"special_character_ratio":0.30649352,"punctuation_ratio":0.08547009,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99997425,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-27T10:38:18Z\",\"WARC-Record-ID\":\"<urn:uuid:5b4011ae-6ba2-4aa8-8ce2-d9f8122b9a00>\",\"Content-Length\":\"140744\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:67c5c382-a7df-4bf4-aac4-536cd7a8c8e2>\",\"WARC-Concurrent-To\":\"<urn:uuid:c652e742-e73c-4e4e-a2a5-664bcf9c4ea4>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/96194/interpolating-bijections-of-point-sets-in-euclidean-space\",\"WARC-Payload-Digest\":\"sha1:2RXI5QSSUM6B2GSGMUBSBTDOPCGZRIPN\",\"WARC-Block-Digest\":\"sha1:7VTGUGTGN3Q4VJKCFJLLRXRM4ZLFORHU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323588113.25_warc_CC-MAIN-20211027084718-20211027114718-00656.warc.gz\"}"}