Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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$. –  Lee Mosher May 7 '12 at 13:29
That's a typo, I intended $\leq$. Fixing it now. –  Vidit Nanda May 7 '12 at 15:18

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
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}$. –  Vidit Nanda 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. –  Lee Mosher May 7 '12 at 15:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.