Interpolating Bijections of Point Sets in Euclidean Space

2012-05-07T08:44:54Z

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

Answer by Lee Mosher for Interpolating Bijections of Point Sets in Euclidean Space

2012-05-07T13:51:29Z

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.

Interpolating Bijections of Point Sets in Euclidean Space - MathOverflow

Interpolating Bijections of Point Sets in Euclidean Space

Answer by Lee Mosher for Interpolating Bijections of Point Sets in Euclidean Space