## 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