Let $P = \{p_1,\ldots,p_n\}$ and $Q = \{q_1,\ldots,q_n\}$
be two point sets lying in the interior of rectangles in the plane.
We show how to construct a piecewise linear homeomorphism
of size $O(n^2)$ between the rectangles which maps $p_i$ to $q_i$
for each $i$. This bound is optimal in the worst case;
i.e., there exist point sets for which any piecewise linear homeomorphism
has size $\Omega(n^2)$.
DIMACS Home Page