2
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Lee Mosher
    Commented May 7, 2012 at 13:29
  • $\begingroup$ That's a typo, I intended $\leq$. Fixing it now. $\endgroup$
    – Vidit Nanda
    Commented May 7, 2012 at 15:18

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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}$. $\endgroup$
    – Vidit Nanda
    Commented May 7, 2012 at 15:23
  • $\begingroup$ 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. $\endgroup$
    – Lee Mosher
    Commented May 7, 2012 at 15:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .