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



Interpolating Bijections of Point Sets in Euclidean Space
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.


