2 Fixed a typo as per Lee Mosher's suggestion!

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$?

1

# 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)] < \alpha\cdot\max_{i,j}[m(\phi_{ij})]$ for some $\alpha < 1$?