DIMACS TR: 94-52
Constructing Piecewise Linear Hemomorphisms
Authors: Diane Souvaine and Rephael Wenger
ABSTRACT
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)$.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-52.ps
DIMACS Home Page