Interpolating Bijections of Point Sets in Euclidean Space - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T06:47:30Z http://mathoverflow.net/feeds/question/96194 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96194/interpolating-bijections-of-point-sets-in-euclidean-space Interpolating Bijections of Point Sets in Euclidean Space Vidit Nanda 2012-05-07T08:44:54Z 2012-05-07T15:18:46Z <p>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)\|$.</p> <p>We may now associated a number $m(\phi)$ to $\phi$, namely the maximal edge length in $G_\phi$. Then,</p> <blockquote> <p>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)$</p> </blockquote> <p>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:</p> <blockquote> <p>What hypotheses are needed to similarly interpolate between $k$ point sets $P_1, \ldots P_k$ with pairwise bijections defined for $k > 2$? </p> </blockquote> <p>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 &lt; 1$? </p> http://mathoverflow.net/questions/96194/interpolating-bijections-of-point-sets-in-euclidean-space/96215#96215 Answer by Lee Mosher for Interpolating Bijections of Point Sets in Euclidean Space Lee Mosher 2012-05-07T13:51:29Z 2012-05-07T13:51:29Z <p>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.</p>